fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdlib>
  23. #include <cassert>
  24. #include <climits>
  25. #include <cctype>
  26.  
  27. #define len(c) sizeof(c)/4
  28. #define print(c,n) for(int ix = 0; ix < n; ix++) cout <<c[ix]<<" ";cout<<endl;
  29. #define MAXN 200000
  30. #define N 800005
  31. #define ll long long;
  32. #define REP(i,a) for(int i=0;i<int(a);i++)
  33.  
  34. int A[MAXN];
  35. int A2[MAXN];
  36. int T[N];
  37.  
  38. using namespace std;
  39.  
  40.  
  41.  
  42. int LP[N];
  43.  
  44. void build(int node, int a, int b){
  45.     int m=(a+b)/2,r=node*2,l=node*2+1;
  46.     if(a==b){
  47.         T[node]=0;
  48.         return;
  49.     }
  50.     build(r, a,m);
  51.     build(l, m+1,b);
  52.     //    for (int i=0; i<3; i++) {
  53.     //        T[node][i] = T[node*2][i]+T[node*2+1][i];
  54.     //    }
  55. //    T[node]=T[r]+T[l];
  56. }
  57.  
  58. void push(int node, int a, int b){
  59.     int n=LP[node];
  60.     if(n>0){
  61.         if(a!=b){
  62.             LP[node*2]+=n;
  63.             LP[node*2+1]+=n;
  64.         }
  65.         T[node]+=LP[node];
  66.         LP[node]=0;
  67.     }
  68. }
  69.  
  70. void update(int node, int a, int b, int i, int j){
  71.     int m=(a+b)/2,r=node*2,l=node*2+1;
  72.     push(node,a,b);
  73.     if(i>b || j<a)
  74.         return;
  75.     if(a>=i && b<=j){
  76.         LP[node]++;
  77.         return;
  78.     }
  79.     update(r, a,m,i,j);
  80.     update(l, m+1,b,i,j);
  81. //    T[node] = T[r]+T[l];
  82. }
  83.  
  84. void query(int node, int a, int b){
  85.     int m=(a+b)/2,r=node*2,l=node*2+1;
  86.     push(node,a,b);
  87.     if(a==b){
  88.         A2[b]=T[node];
  89.         return;
  90.     }
  91.     query(r,a,m);
  92.     query(l,m+1,b);
  93. }
  94.  
  95.  
  96. int main()
  97. {
  98. //    cout<<"xxx";
  99.     int n,q;
  100.     cin>>(n);
  101.     cin>>(q);
  102.     REP(i,n)scanf("%d",&A[i]);
  103.     sort(A,A+n);
  104. //    print(A,n);
  105.     for(int i=0;i<q;i++){
  106.             int a,b;
  107.             cin>>(a);
  108.             cin>>(b);
  109.             update(1, 0, n-1, a-1, b-1);
  110.     }
  111.     query(1,0,n-1);
  112.     sort(A2,A2+n);
  113.     long long r= 0;
  114.     for (int i =0; i<n; i++) {
  115.         r+=(long long)A[i]*(long long)A2[i];
  116.     }
  117.     cout<<r;
  118.     return 0;
  119. }
  120.  
  121.  
Success #stdin #stdout 0s 10672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fsUknS
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!