Submission #988670

#	Time	Username	Problem	Language	Result	Execution time	Memory
988670		mannshah1211	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	151 ms	7860 KiB

sterilizing

/**
 *    author: tourist
 *    created:
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

class segtree {
  #define lc 2 * v + 1
  #define rc 2 * v + 2
  #define m (ll + rr) / 2
  #define pul(v) tree[v] = unite(tree[lc], tree[rc])
 public:
  struct node {
    int mx = 0;
    long long sum = 0;
    
    node() {} 
    
    node(int x) : mx(x), sum(x) {} 
  };
  
  node unite(const node &a, const node &b) const {
    node res;
    res.mx = max(a.mx, b.mx);
    res.sum = a.sum + b.sum;
    return res;
  }
  
  vector<node> tree;
  int n;
  
  segtree(int _n) {
    n = 1;
    while (n < _n) {
      n <<= 1;
    }
    tree.resize(2 * n);
  }
  
  void modify(int p, int x, int v, int ll, int rr) {
    if (rr - ll == 1) {
      tree[v] = node(x);
      return;
    }
    if (p < m) {
      modify(p, x, lc, ll, m);
    } else {
      modify(p, x, rc, m, rr);
    }
    pul(v);
  }
  
  void modify(int p, int x) {
    modify(p, x, 0, 0, n);
  }
  
  void spray(int l, int r, int k, int v, int ll, int rr) {
    if (ll >= r || l >= rr || tree[v].mx == 0) {
      return;
    }
    if (rr - ll == 1) {
      tree[v] = node(tree[v].mx / k);
      return;
    }
    spray(l, r, k, lc, ll, m);
    spray(l, r, k, rc, m, rr);
    pul(v);
  }
  
  void spray(int l, int r, int k) {
    if (k == 1) {
      return;
    }
    spray(l, r, k, 0, 0, n);
  }
  
  long long sum(int l, int r, int v, int ll, int rr) {
    if (ll >= r || l >= rr) {
      return int64_t(0);
    }
    if (ll >= l && rr <= r) {
      return tree[v].sum;
    }
    return sum(l, r, lc, ll, m) + sum(l, r, rc, m, rr);
  }
  
  long long sum(int l, int r) {
    return sum(l, r, 0, 0, n);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q, k;
  cin >> n >> q >> k;
  segtree seg(n);
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    seg.modify(i, a[i]);
  }
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int p, x;
      cin >> p >> x;
      --p;  
      seg.modify(p, x);
    } else if (op == 2) {
      int l, r;
      cin >> l >> r;
      --l; --r;
      seg.spray(l, r + 1, k);
    } else {
      int l, r;
      cin >> l >> r;
      --l; --r;
      cout << seg.sum(l, r + 1) << '\n';
    }
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75