oj.uz

Submission #988670

# Submission time Handle Problem Language Result Execution time Memory
988670 2024-05-25T13:05:24 Z mannshah1211 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 151 ms 7860 KB 
/**
 *    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5000 KB Output is correct
2 Correct 35 ms 4444 KB Output is correct
3 Correct 34 ms 6744 KB Output is correct
4 Correct 42 ms 7372 KB Output is correct
5 Correct 50 ms 7860 KB Output is correct
6 Correct 51 ms 7776 KB Output is correct
7 Correct 49 ms 7800 KB Output is correct
8 Correct 51 ms 7708 KB Output is correct
9 Correct 46 ms 7504 KB Output is correct
10 Correct 46 ms 7508 KB Output is correct
11 Correct 48 ms 7508 KB Output is correct
12 Correct 46 ms 7772 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1316 KB Output is correct
2 Correct 12 ms 2908 KB Output is correct
3 Correct 15 ms 2908 KB Output is correct
4 Correct 35 ms 2616 KB Output is correct
5 Correct 49 ms 6224 KB Output is correct
6 Correct 49 ms 6220 KB Output is correct
7 Correct 44 ms 6484 KB Output is correct
8 Correct 50 ms 6224 KB Output is correct
9 Correct 46 ms 6228 KB Output is correct
10 Correct 45 ms 6104 KB Output is correct
11 Correct 45 ms 6228 KB Output is correct
12 Correct 48 ms 6224 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4180 KB Output is correct
2 Correct 63 ms 4376 KB Output is correct
3 Correct 68 ms 4176 KB Output is correct
4 Correct 75 ms 3408 KB Output is correct
5 Correct 105 ms 7668 KB Output is correct
6 Correct 99 ms 7508 KB Output is correct
7 Correct 88 ms 7508 KB Output is correct
8 Correct 116 ms 7512 KB Output is correct
9 Correct 107 ms 7400 KB Output is correct
10 Correct 118 ms 7508 KB Output is correct
11 Correct 90 ms 7508 KB Output is correct
12 Correct 151 ms 7484 KB Output is correct