fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define F first
  4. #define S second
  5. #define mp make_pair
  6. #define All(v) v.begin(),v.end()
  7. #define mod  1000000007
  8. #define write freopen("output.txt","w",stdout)
  9. #define read freopen("test (1).txt","r",stdin)
  10. #define FIO std::ios_base::sync_with_stdio(false);
  11. using namespace std;
  12. int a[100005],timer;
  13. ll square[4*100005];
  14. int suming[4*100005];
  15. int lazy1[4*100005],lazy2[4*100005];
  16. int t1[4*100005],t2[4*100005];
  17.  
  18. void init()
  19. {
  20.     memset(square,0,sizeof(square));
  21.     memset(suming,0,sizeof(suming));
  22.     memset(lazy1,0,sizeof(lazy1));
  23.     memset(lazy2,0,sizeof(lazy2));
  24.     memset(t1,0,sizeof(t1));
  25.     memset(t2,0,sizeof(t2));
  26. }
  27. void shift(int node,int L,int R)
  28. {
  29.     if(t1[node] > t2[node])
  30.     {
  31.         if(lazy1[node])
  32.         {
  33.             int val = lazy1[node];
  34.             int len = R-L+1;
  35.             square[node] = (square[node] + 2LL * val * suming[node] + len * val * val);
  36.             suming[node] += (1LL * len * val);
  37.  
  38.             if(t1[2*node] > t2[2*node])
  39.             {
  40.                 lazy1[2*node] += lazy1[node];
  41.                 lazy1[2*node] += lazy1[node];
  42.                 t1[2*node] = t1[node];
  43.             }
  44.             else
  45.             {
  46.                 lazy2[2*node] += lazy1[node];
  47.                 lazy2[2*node] += lazy1[node];
  48.                 t2[2*node] = t1[node];
  49.             }
  50.             if(t1[2*node+1] > t2[2*node+1]) 
  51.             {
  52.                 lazy1[2*node+1] += lazy1[node];
  53.                 lazy1[2*node+1] += lazy1[node];
  54.                 t1[2*node+1] = t1[node];
  55.             }
  56.             else
  57.             {
  58.                 lazy2[2*node+1] += lazy1[node];
  59.                 lazy2[2*node+1] += lazy1[node];
  60.                 t2[2*node+1] = t1[node];
  61.             }
  62.         }
  63.         lazy1[node] = 0;
  64.     }
  65.     else
  66.     {
  67.         if(lazy2[node])
  68.         {
  69.             int val = lazy2[node];
  70.             int len = R-L+1;
  71.             square[node] = 1LL * len * val * val;
  72.             suming[node] = (1LL * len * val);
  73.             if(t1[2*node] > t2[2*node]) /// time increment
  74.             {
  75.                 lazy1[2*node] += lazy2[node];
  76.                 lazy1[2*node] += lazy2[node];
  77.                 t1[2*node] = t2[node];
  78.             }
  79.             else
  80.             {
  81.                 lazy2[2*node] += lazy2[node];
  82.                 lazy2[2*node] += lazy2[node];
  83.                 t2[2*node] = t2[node];
  84.             }
  85.  
  86.  
  87.             if(t1[2*node+1] > t2[2*node+1]) /// time increment
  88.             {
  89.                 lazy1[2*node+1] += lazy2[node];
  90.                 lazy1[2*node+1] += lazy2[node];
  91.                 t1[2*node+1] = t2[node];
  92.             }
  93.             else
  94.             {
  95.                 lazy2[2*node+1] += lazy2[node];
  96.                 lazy2[2*node+1] += lazy2[node];
  97.                 t2[2*node+1] = t2[node];
  98.             }
  99.         }
  100.         lazy2[node] = 0;
  101.     }
  102.     t1[node] = t2[node] = 0;
  103. }
  104. void update1(int node,int L,int R,int l,int r,int val) /// add val to all number [l,r]
  105. {
  106.     shift(node,L,R);
  107.     if(L > R || L > r || R < l)
  108.         return ;
  109.     if(L >= l && R <= r)
  110.     {
  111.         lazy1[node] = val;
  112.         t1[node] = timer;
  113.         shift(node,L,R);
  114.         return ;
  115.     }
  116.  
  117.     int mid = (L+R)/2;
  118.     update1(2*node,L,mid,l,r,val);
  119.     update1(2*node+1,mid+1,R,l,r,val);
  120.  
  121.     square[node] = square[2*node] + square[2*node+1];
  122.     suming[node] = suming[2*node] + suming[2*node+1];
  123.  
  124. }
  125. void update2(int node,int L,int R,int l,int r,int x) /// set x to all number [l,r]
  126. {
  127.     shift(node,L,R);
  128.     if(L > R || L > r || R < l)
  129.         return ;
  130.     if(L >= l && R <= r)
  131.     {
  132.         lazy2[node] = x;
  133.         t2[node] = timer;
  134.         square[node] = 0;
  135.         suming[node] = 0;
  136.         shift(node,L,R);
  137.         return ;
  138.     }
  139.  
  140.     int mid = (L+R)/2;
  141.     update2(2*node,L,mid,l,r,x);
  142.     update2(2*node+1,mid+1,R,l,r,x);
  143.  
  144.     square[node] = square[2*node] + square[2*node+1];
  145.     suming[node] = suming[2*node] + suming[2*node+1];
  146.  
  147. }
  148. void build(int node,int L,int R)
  149. {
  150.     if(L == R)
  151.     {
  152.         square[node] = 1LL * a[L] * a[L];
  153.         suming[node] = a[L];
  154.         return ;
  155.     }
  156.     int mid = (L+R)/2;
  157.     build(2*node,L,mid);
  158.     build(2*node+1,mid+1,R);
  159.  
  160.     square[node] = square[2*node] + square[2*node+1];
  161.     suming[node] = suming[2*node] + suming[2*node+1];
  162. }
  163. ll query(int node,int L,int R,int l,int r)
  164. {
  165.     if(L > R || L > r || R < l)
  166.         return 0;
  167.  
  168.     shift(node,L,R);
  169.  
  170.     if(L >= l && R <= r)
  171.         return square[node];
  172.  
  173.     int mid = (L + R) / 2;
  174.     ll sum1 = query(node*2, L, mid, l, r);
  175.     ll sum2 = query(node*2 + 1, mid + 1, R, l, r);
  176.     return (sum1 + sum2);
  177. }
  178.  
  179. int main()
  180. {
  181.     int t,num = 1;
  182.     cin >> t;
  183.     while(t--)
  184.     {
  185.         printf("Case %d:\n",num++);
  186.         init();
  187.         timer = 0;
  188.         int n,q;
  189.         cin >> n >> q;
  190.         for(int i=0; i<n; i++)
  191.             scanf("%d",&a[i]);
  192.         build(1,0,n-1);
  193.         while(q--)
  194.         {
  195.             timer++;
  196.             int c,x,y,z;
  197.             scanf("%d",&c);
  198.             if(c == 2)
  199.             {
  200.                 scanf("%d%d",&x,&y);
  201.                 ll ans = query(1,0,n-1,x-1,y-1);
  202.                 printf("%I64d\n",ans);
  203.             }
  204.             else
  205.             {
  206.                 scanf("%d%d%d",&x,&y,&z);
  207.                 if(c == 1)
  208.                     update1(1,0,n-1,x-1,y-1,z);
  209.                 else
  210.                     update2(1,0,n-1,x-1,y-1,z);
  211.  
  212.             }
  213.         }
  214.     }
  215.  
  216.  
  217.  
  218.     return 0;
  219. }
  220.  
Time limit exceeded #stdin #stdout 5s 14080KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/fsLnGd
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!