fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. long long segtree[400000], lazy[400000];
  5.  
  6. void propagate(int root, int l, int r) {
  7.   segtree[root] += lazy[root] * (r-l+1);
  8.   if(l != r) {
  9.     lazy[2*root+1] += lazy[root];
  10.     lazy[2*root+2] += lazy[root];
  11.   }
  12.   lazy[root] = 0;
  13. }
  14.  
  15. long long query(int root, int l, int r, int a, int b) {
  16.   if(b < l || r < a) return 0;
  17.  
  18.   propagate(root, l, r);
  19.   if(a <= l && r <= b) return segtree[root];
  20.  
  21.   int mid = (l+r)/2;
  22.   return query(2*root+1, l, mid, a, b) + query(2*root+2, mid+1, r, a, b);
  23. }
  24.  
  25. void update(int root, int l, int r, int a, int b, int val) {
  26.   if(b < l || r < a) return;
  27.   if(a <= l && r <= b) { lazy[root] += val; return; }
  28.  
  29.   int mid = (l+r)/2;
  30.   update(2*root+1, l, mid, a, b, val);
  31.   update(2*root+2, mid+1, r, a, b, val);
  32.  
  33.   propagate(2*root+1, l, mid);
  34.   propagate(2*root+2, mid+1, r);
  35.   segtree[root] = segtree[2*root+1] + segtree[2*root+2];
  36. }
  37.  
  38. int main() {
  39.   int t;
  40.   scanf("%d", &t);
  41.  
  42.   while(t--) {
  43.     int n, c;
  44.     scanf("%d %d", &n, &c);
  45.  
  46.     memset(segtree, 0, sizeof segtree);
  47.     memset(lazy, 0, sizeof lazy);
  48.  
  49.     for(int i = 0; i < c; i++) {
  50.       int type;
  51.       scanf("%d", &type);
  52.  
  53.       int p, q, v;
  54.       if(type == 0) {
  55.         scanf("%d %d %d", &p, &q, &v);
  56.         update(0, 0, n-1, p-1, q-1, v);
  57.       } else if(type == 1) {
  58.         scanf("%d %d", &p, &q);
  59.         printf("%lld\n", query(0, 0, n-1, p-1, q-1));
  60.       }
  61.     }         
  62.   }
  63. }
  64.  
Time limit exceeded #stdin #stdout 5s 8976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KeXgz
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!