fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 2e5 + 5;
  5.  
  6. long long n, m,i,k;
  7. long long a[MaxN];
  8. long long st[4 * MaxN], lazy[4 * MaxN];
  9.  
  10. void build(long long id, long long l, long long r)
  11. {
  12.     if(l == r)
  13.     {
  14.         st[id] = a[l];
  15.         return;
  16.     }
  17.  
  18.     long long mid = (l + r) / 2;
  19.  
  20.     build(id * 2, l, mid);
  21.     build(id * 2 + 1, mid + 1, r);
  22.  
  23.     st[id] = st[id * 2] + st[id * 2 + 1];
  24. }
  25.  
  26. void push(long long id, long long l, long long r)
  27. {
  28.     if(lazy[id] == 0)
  29.         return;
  30.  
  31.     long long mid = (l + r) / 2;
  32.  
  33.     st[id * 2] += lazy[id] * (mid - l + 1);
  34.     st[id * 2 + 1] += lazy[id] * (r - mid);
  35.  
  36.     lazy[id * 2] += lazy[id];
  37.     lazy[id * 2 + 1] += lazy[id];
  38.  
  39.     lazy[id] = 0;
  40. }
  41.  
  42. void update(long long id, long long l, long long r,
  43.             long long u, long long v, long long val)
  44. {
  45.     if(v < l || r < u)
  46.         return;
  47.  
  48.     if(u <= l && r <= v)
  49.     {
  50.         st[id] += val * (r - l + 1);
  51.         lazy[id] += val;
  52.         return;
  53.     }
  54.  
  55.     push(id, l, r);
  56.  
  57.     long long mid = (l + r) / 2;
  58.  
  59.     update(id * 2, l, mid, u, v, val);
  60.     update(id * 2 + 1, mid + 1, r, u, v, val);
  61.  
  62.     st[id] = st[id * 2] + st[id * 2 + 1];
  63. }
  64.  
  65. long long query(long long id, long long l, long long r,
  66.                 long long u, long long v)
  67. {
  68.     if(v < l || r < u)
  69.         return 0;
  70.  
  71.     if(u <= l && r <= v)
  72.         return st[id];
  73.  
  74.     push(id, l, r);
  75.  
  76.     long long mid = (l + r) / 2;
  77.  
  78.     return query(id * 2, l, mid, u, v)
  79.          + query(id * 2 + 1, mid + 1, r, u, v);
  80. }
  81.  
  82. int main()
  83. {
  84.     cin >> n >> m;
  85.     for (long long i=1; i<=m; i++)
  86.     {
  87.         cin >> i >> k;
  88.         if(k<=n)
  89.         {
  90.             update(1,1,2*n,i,i+k-1,1);
  91.         }
  92.         else
  93.         {
  94.             long long t= k/n;
  95.             update(1,1,2*n,i,i+n-1,t);
  96.             long long x = k%n;
  97.             update(1,1,2*n,i-1,i-1+x-1,1);
  98.         }
  99.     }
  100.     for (long long i=1; i<=n; i++)
  101.     {
  102.         cout << query(1,1,n,i,i) +query(1,1,n,i+n,i+n) << " ";
  103.     }
  104. }
  105.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6rwjE9
language:
C++14 (gcc 8.3)
created:
3 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!