fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. const int MAXN = 300005;
  10.  
  11. struct Mast {
  12.     int s, a;
  13. };
  14.  
  15. Mast active_masts[MAXN];
  16. ll tree[4 * MAXN];
  17. ll lazy_c[4 * MAXN];
  18. ll lazy_d[4 * MAXN];
  19.  
  20. inline ll sum_range(ll L, ll R) {
  21.     if (L > R) return 0;
  22.     return (L + R) * (R - L + 1) / 2;
  23. }
  24.  
  25. void push(int v, int tl, int tr) {
  26.     if (lazy_c[v] == 0 && lazy_d[v] == 0) return;
  27.     int tm = (tl + tr) / 2;
  28.  
  29.     ll lc = lazy_c[v];
  30.     ll ld = lazy_d[v];
  31.  
  32.     tree[2 * v] += (ll)(tm - tl + 1) * lc + ld * sum_range(tl, tm);
  33.     lazy_c[2 * v] += lc;
  34.     lazy_d[2 * v] += ld;
  35.  
  36.     tree[2 * v + 1] += (ll)(tr - tm) * lc + ld * sum_range(tm + 1, tr);
  37.     lazy_c[2 * v + 1] += lc;
  38.     lazy_d[2 * v + 1] += ld;
  39.  
  40.     lazy_c[v] = 0;
  41.     lazy_d[v] = 0;
  42. }
  43.  
  44. void update(int v, int tl, int tr, int l, int r, ll c, ll d) {
  45.     if (l > r) return;
  46.     if (l == tl && r == tr) {
  47.         tree[v] += (ll)(tr - tl + 1) * c + d * sum_range(tl, tr);
  48.         lazy_c[v] += c;
  49.         lazy_d[v] += d;
  50.     } else {
  51.         push(v, tl, tr);
  52.         int tm = (tl + tr) / 2;
  53.         update(2 * v, tl, tm, l, min(r, tm), c, d);
  54.         update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, c, d);
  55.         tree[v] = tree[2 * v] + tree[2 * v + 1];
  56.     }
  57. }
  58.  
  59. ll query(int v, int tl, int tr, int l, int r) {
  60.     if (l > r) return 0;
  61.     if (l == tl && r == tr) return tree[v];
  62.     push(v, tl, tr);
  63.     int tm = (tl + tr) / 2;
  64.     return query(2 * v, tl, tm, l, min(r, tm)) + query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
  65. }
  66.  
  67. int main() {
  68.     ios_base::sync_with_stdio(false);
  69.     cin.tie(NULL);
  70.  
  71.     int n, m;
  72.     if (!(cin >> n >> m)) return 0;
  73.  
  74.     for (int i = 0; i < m; ++i) {
  75.         char type;
  76.         cin >> type;
  77.         if (type == 'P') {
  78.             int x, s, a;
  79.             cin >> x >> s >> a;
  80.             active_masts[x] = {s, a};
  81.             int k = (s - 1) / a;
  82.             int Lm = max(1, x - k);
  83.             int Rm = min(n, x + k);
  84.             update(1, 1, n, Lm, x, (ll)s - (ll)a * x, (ll)a);
  85.             update(1, 1, n, x + 1, Rm, (ll)s + (ll)a * x, -(ll)a);
  86.         } else if (type == 'U') {
  87.             int x;
  88.             cin >> x;
  89.             int s = active_masts[x].s;
  90.             int a = active_masts[x].a;
  91.             int k = (s - 1) / a;
  92.             int Lm = max(1, x - k);
  93.             int Rm = min(n, x + k);
  94.             update(1, 1, n, Lm, x, -((ll)s - (ll)a * x), -(ll)a);
  95.             update(1, 1, n, x + 1, Rm, -((ll)s + (ll)a * x), (ll)a);
  96.         } else if (type == 'Z') {
  97.             int x1, x2;
  98.             cin >> x1 >> x2;
  99.             ll total_sum = query(1, 1, n, x1, x2);
  100.             ll count = (ll)x2 - x1 + 1;
  101.             cout << total_sum / count << "\n";
  102.         }
  103.     }
  104.  
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 7672KB
comments (?)
stdin
copy 
11 7
P 5 30 10
Z 6 7
P 10 22 5
Z 6 7
Z 6 6
U 5
Z 6 6
stdout
copy 
15
19
22
2
https://ideone.com/CHIhaS
language:
C++14 (gcc 8.3)
created:
14 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!