fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <vector>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <map>
  13. #include <set>
  14. using namespace std;
  15.  
  16. #define rep(i, n)     for (int(i) = int(1); int(i) <= int(n); ++i)
  17. #define repd(i, n)    for (int(i) = int(n); int(i) >= int(1); --i)
  18. #define FOR(i, l, r)  for (int(i) = int(l); int(i) <= int(r); ++i)
  19. #define FORD(i, l, r) for (int(i) = int(r); int(i) >= int(l); --i)
  20. #define hashmap unordered_map
  21. #define hashset unordered_set
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define mp make_pair
  26. #define mt make_tuple
  27. #define all(x) (x).begin(), (x).end()
  28. #define rall(x) (x).rbegin(), (x).rend()
  29. #define itr iterator
  30. #define rtr reverse_iterator
  31.  
  32. typedef long long       ll;     typedef unsigned long long  ull;
  33. typedef pair<int, int>  pi;     typedef pair<ll, ll>    pll;
  34. typedef set<int>        si;     typedef vector<si>      vsi;
  35. typedef set<ll>         sll;    typedef vector<sll>     vsll;
  36. typedef set<pi>         spi;    typedef vector<spi>     vspi;
  37. typedef set<pll>        spll;   typedef vector<spll>    vspll;
  38. typedef vector<string>  vs;     typedef vector<vs>      vms;
  39. typedef vector<bool>    vb;     typedef vector<vb>      vmb;
  40. typedef vector<char>    vc;     typedef vector<vc>      vmc;
  41. typedef vector<int>     vi;     typedef vector<vi>      vmi;    
  42. typedef vector<ll>      vll;    typedef vector<vll>     vmll;
  43. typedef vector<pi>      vpi;    typedef vector<vpi>     vmpi;
  44. typedef vector<pll>     vpll;   typedef vector<vpll>    vmpll;
  45.  
  46. inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
  47. inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
  48. inline void getInt(int& n) {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();    n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';      if(sign)n=-n;}
  49. inline void getLong(ll& n) {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();    n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';      if(sign)n=-n;}
  50. inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
  51. char bufWrite[20];
  52. template<typename T>inline void writeInt(T x)               {if(x<0)putchar('-'),x=-x;char*bufPos=bufWrite;do{*bufPos++=x%10+'0';}while(x/=10);do{putchar(*--bufPos);}while(bufPos>bufWrite);}
  53. template<typename T>inline void printInt(T x, char c = EOF) {if(x<0)putchar('-'),x=-x;char*bufPos=bufWrite;do{*bufPos++=x%10+'0';}while(x/=10);do{putchar(*--bufPos);}while(bufPos>bufWrite);if(c!=EOF)putchar(c);}
  54. template<typename T>inline T gcd(T a,T b){while(b!=0)swap(b,a%=b);return a;}
  55. template<typename T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  56. template<typename T>inline tuple<T,T,T>extgcd(T a,T b){if(!a)return mt(b,0,1);T g,x,y;tie(g,x,y)=extgcd(b%a,a);return mt(g,y-(b/a)*x,x);}
  57. template <class T> T    bitGet    (T  x, int bit)           { return T(1) & (x >> (bit - 1)); }
  58. template <class T> void bitSet    (T &x, int bit)           { x |=  (T(1) << (bit - 1)); }
  59. template <class T> void bitReset  (T &x, int bit)           { x &= ~(T(1) << (bit - 1)); }
  60. template <class T> void bitFlip   (T &x, int bit)           { x ^=  (T(1) << (bit - 1)); }
  61. template <class T> void bitMake   (T &x, int bit, bool val) { x ^=  (T(1) << (bit - 1)) & (-val ^ x); }
  62. /// ======================================================================
  63. /// ======================================================================
  64.  
  65. int query()
  66. {
  67.  
  68.  
  69.     return 0;
  70. }
  71.  
  72. int main()
  73. {
  74.     int n = readInt();
  75.     int q = readInt();
  76.  
  77.     vi a(n);
  78.     for (int &x : a) x = readInt();
  79.     sort(all(a));
  80.  
  81.     vi m(n + 1, 0);
  82.     while (q--)
  83.     {
  84.         /// left+ || right-
  85.         m[readInt() - 1]++;
  86.         m[readInt()]--;
  87.     }
  88.  
  89.     vi b(n);
  90.     int fre = 0;
  91.     for (int i = 0; i < n; ++i)
  92.     {
  93.         fre += m[i];
  94.         b[i] = fre;
  95.     }
  96.     sort(all(b));
  97.  
  98.     ll res = 0;
  99.     for (int i = 0; i < n; ++i)
  100.         res += 1LL * a[i] * b[i];
  101.  
  102.     cout << res;
  103.     return 0;
  104. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
6 6
1 2 3 1 2 3
1 2
2 3
1 3
2 4
3 4
1 4
stdout
copy 
42
https://ideone.com/wbWblr
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!