fork download
copy 
  1. #include<algorithm>
  2. #include<iostream>
  3. #include<sstream>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<climits>
  7. #include<fstream>
  8. #include<cctype>
  9. #include<cstdio>
  10. #include<string>
  11. #include<vector>
  12. #include<queue>
  13. #include<stack>
  14. #include<cmath>
  15. #include<map>
  16. #include<set>
  17. using namespace std;
  18.  
  19. #define pb push_back
  20. #define mp make_pair
  21. #define Y second
  22. #define X first
  23.  
  24. #define fi freopen("input.txt","r",stdin)
  25. #define fo freopen("output.txt","w",stdout)
  26.  
  27. const double pi     =   acos(-1.0);
  28. const double eps    =   1e-8;
  29.  
  30. template <class T>
  31. inline void read(T &i)
  32. {
  33. bool minus=false;
  34. char c;
  35. for(c=getchar();(c<'0'||c>'9')&&(c!='-');c=getchar());
  36. if(c=='-')
  37. {minus=true;
  38. c='0';}
  39. for(i=0;c>='0'&&c<='9';c=getchar())
  40. i=(i<<3)+(i<<1) + (c-48);
  41. if(minus)
  42. i=(~i)+1;
  43. }
  44.  
  45. vector <string> parse(string s, string c)
  46. {
  47.   int len = c.length(), p = -len, np;
  48.   vector <string> ans;
  49.  
  50.   do
  51.     {
  52.       np = s.find(c, p+len);
  53.       ans.push_back(s.substr(p+len, np - p - len));
  54.       p = np;
  55.     }
  56.   while (p != string::npos);
  57.  
  58.   return ans;
  59. }
  60.  
  61. inline int max2(int a, int b) {
  62.     return ((a > b)? a : b);
  63. }
  64.  
  65. inline int max3(int a, int b, int c) {
  66.     return max2(a, max2(b, c));
  67. }
  68.  
  69. /*Solution code starts here */
  70.  
  71. #define maxn 300009
  72. #define maxt 2060009
  73.  
  74. long long int Array[maxn];
  75. int n;
  76.  
  77.  
  78. class node
  79. {
  80.       public:
  81.  
  82.    int st,ed;
  83.    long long add,sum;
  84.  
  85.    node()
  86.     {add=0,sum=0;
  87.     }
  88.  
  89.    node(int l , int r)
  90.    { st=l;
  91.      ed=r;
  92.      add=0;sum=0;
  93.     } 
  94.  
  95.  
  96.  
  97.     void merge(node L,node R)
  98.     { 
  99.      if( L.st==-1)
  100.         sum=R.sum+R.add*(R.ed-R.st+1);        
  101.      else if( R.st==-1)
  102.         sum= L.sum + L.add*(L.ed-L.st+1);  
  103.      else
  104.         sum= L.sum + L.add*(L.ed-L.st+1) + R.sum + R.add*(R.ed-R.st+1);  
  105.  
  106.     } 
  107.  
  108.     void split( node& L ,  node& R )
  109.      {
  110.         sum+=add*(ed-st+1);
  111.  
  112.         if(ed!=st)
  113.         { L.add+=add;
  114.           R.add+=add;
  115.         }      
  116.  
  117.          add=0;
  118.     }//end spilt    
  119.  
  120.  
  121. };    
  122.  
  123. node ident;
  124. node Tree[maxt];
  125.  
  126. class SegmentTree
  127. {
  128.       public:
  129.  
  130.  
  131.  
  132.  
  133.             void build(int  no ,int  l , int   r)
  134.              {
  135.  
  136.                if(r==l)
  137.                 { Tree[no].st=Tree[no].ed=r;
  138.                   Tree[no].sum=Array[r];
  139.                   Tree[no].add=0;               
  140.                   return ;
  141.                 }
  142.  
  143.                 int  lc=2*no;
  144.                 int  rc=2*no+1;
  145.  
  146.                 int  mid=(l+r)/2;
  147.  
  148.                 build(lc,l,mid);
  149.                 build(rc,mid+1,r); 
  150.  
  151.                 Tree[no]=node(l,r);               
  152.  
  153.                 Tree[no].merge( Tree[lc] , Tree[rc] );                
  154.  
  155.              }  
  156.  
  157.  
  158.  node  query(int   no, int l,int r, int  i, int j)
  159.     {
  160.       int  lc=2*no;
  161.       int rc=2*no+1;
  162.       int mid=(l+r)/2;
  163.  
  164.       if( l >= i && r<=j )// 
  165.         {
  166.           if( Tree[no].add > 0 )
  167.             Tree[no].split( Tree[lc],Tree[rc] );
  168.  
  169.             return Tree[no];
  170.         }  
  171.  
  172.         if( j < l || i > r)
  173.           return ident;
  174.  
  175.  
  176.         if( Tree[no].add >0 )
  177.           Tree[no].split( Tree[lc]  , Tree[rc] );
  178.  
  179.         node a=query(lc,l,    mid,i,j);
  180.         node b=query(rc,mid+1, r, i,j);
  181.  
  182.          node ans;
  183.          ans.merge(a,b);
  184.          return ans;    
  185.  
  186.     } 
  187.  
  188.     void update(int  no ,int l , int r , int i , int j ,int val)
  189.      {
  190.         if( i <=l && j >=r )
  191.          { Tree[no].add+=val;
  192.            Tree[no].split( Tree[2*no],Tree[2*no+1] );
  193.            return ;
  194.          }
  195.  
  196.          if( j < l || i >r )
  197.            return ;
  198.  
  199.           int mid=(l+r)/2;
  200.  
  201.           update(2*no , l,    mid ,i,j,val);
  202.           update(2*no+1,mid+1 ,r  ,i,j,val);
  203.  
  204.           Tree[no].merge( Tree[2*no] , Tree[2*no+1] );       
  205.  
  206.       }                      
  207.  
  208.  
  209. };
  210.  
  211.  
  212. int main()
  213. {
  214.  ident=node(-1,-1);   
  215.  
  216.  
  217. int q;
  218.  
  219.  cin>>n>>q;
  220.  
  221.  
  222.  vector<long long > in;
  223.  long long x,y;
  224.  
  225.  for(int i=0;i<n;i++)
  226.   { cin>>x;
  227.     in.pb(x);
  228.    }   
  229.  
  230.  memset(Array,0 ,sizeof(Array) );
  231.  
  232.  SegmentTree st;
  233.  
  234.   st.build(1,0,n-1);
  235.  
  236.  
  237.      for(int k=1;k<=q;k++)
  238.       {   
  239.          cin>>x>>y;           
  240.         st.update(1,0,n-1,x-1,y-1,1);        
  241.       }  
  242.  
  243.  
  244.   /*  else if(op==1)
  245.             { scanf("%d%d",&x,&y);
  246.               printf("%lld\n",(st.query(1,0,n-1,x-1,y-1) ).sum ); 
  247.              }  
  248.       */
  249.  
  250.       vector<long long > cont;
  251.  
  252.       for(int i=0;i<n;i++)
  253.         {  x=(st.query(1,0,n-1,i,i) ).sum;   
  254.           cont.pb(x);
  255.         } 
  256.  
  257.  
  258.         sort( cont.begin() , cont.end() );
  259.         sort( in.begin() , in.end() );
  260.  
  261.         long long ans=0;
  262.  
  263.         for(int i=0;i<n;i++)
  264.            { //cout<<in[i]<<"  "<<cont[i]<<endl;
  265.           ans=ans+(long long)( in[i]*cont[i] );
  266.           } 
  267.  
  268.           cout<<ans<<endl;        
  269.  
  270.      return 0;
  271. }     
  272.  
  273.  
  274.  
  275.  
Success #stdin #stdout 0.03s 53680KB
comments (?)
stdin
copy 
34 21
23 38 16 49 44 50 48 34 33 19 18 31 11 15 20 47 44 30 39 33 45 46 1 13 27 16 31 36 17 23 38 5 30 16
8 16
14 27
8 26
1 8
5 6
23 28
4 33
13 30
12 30
11 30
9 21
1 14
15 22
4 11
5 24
8 20
17 33
6 9
3 14
25 34
10 17
stdout
copy 
8012
https://ideone.com/RBni19
language:
C++ (gcc 8.3)
created:
11 years 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!