oj.uz

Submission #118959

# Submission time Handle Problem Language Result Execution time Memory
118959 2019-06-20T06:06:14 Z IOrtroiii Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 286 ms 5892 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 100100;

int n, q, k;
int a[N];
ll T[N << 2];

#define mid ((l + r) >> 1)

void build(int v, int l, int r) {
   if (l == r) {
      T[v] = (ll) a[l];
      return;
   }
   build(v << 1, l, mid);
   build(v << 1 | 1, mid + 1, r);
   T[v] = T[v << 1] + T[v << 1 | 1];
}

void mdf(int v, int l, int r, int pos, int val) {
   if (l == r) {
      T[v] = (ll) val;
      return;
   }
   if (pos <= mid) mdf(v << 1, l, mid, pos, val);
   else mdf(v << 1 | 1, mid + 1, r, pos, val);
   T[v] = T[v << 1] + T[v << 1 | 1];
}

void div(int v, int l, int r, int L, int R) {
   if (T[v] == 0 || k == 1) return;
   if (l == r) {
      T[v] /= k;
      return;
   }
   if (L <= mid) div(v << 1, l, mid, L, R);
   if (mid < R) div(v << 1 | 1, mid + 1, r, L, R);
   T[v] = T[v << 1] + T[v << 1 | 1];
}

ll get(int v, int l, int r, int L, int R) {
   if (L <= l && r <= R) return T[v];
   ll ans = 0;
   if (L <= mid) ans += get(v << 1, l, mid, L, R);
   if (mid < R) ans += get(v << 1 | 1, mid + 1, r, L, R);
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n >> q >> k;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
   }
   build(1, 1, n);
   while (q--) {
      int op;
      cin >> op;
      if (op == 1) {
         int pos, val;
         cin >> pos >> val;
         mdf(1, 1, n, pos, val);
      } else if (op == 2) {
         int l, r;
         cin >> l >> r;
         div(1, 1, n, l, r);
      } else {
         int l, r;
         cin >> l >> r;
         cout << get(1, 1, n, l, r) << "\n";
      }
   }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 6 ms 524 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 7 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2040 KB Output is correct
2 Correct 83 ms 3548 KB Output is correct
3 Correct 71 ms 4700 KB Output is correct
4 Correct 90 ms 5240 KB Output is correct
5 Correct 108 ms 5752 KB Output is correct
6 Correct 109 ms 5724 KB Output is correct
7 Correct 114 ms 5892 KB Output is correct
8 Correct 115 ms 5724 KB Output is correct
9 Correct 106 ms 5612 KB Output is correct
10 Correct 106 ms 5624 KB Output is correct
11 Correct 105 ms 5628 KB Output is correct
12 Correct 107 ms 5624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 512 KB Output is correct
2 Correct 21 ms 1536 KB Output is correct
3 Correct 30 ms 1508 KB Output is correct
4 Correct 88 ms 1024 KB Output is correct
5 Correct 105 ms 2816 KB Output is correct
6 Correct 110 ms 2816 KB Output is correct
7 Correct 105 ms 3008 KB Output is correct
8 Correct 106 ms 2816 KB Output is correct
9 Correct 103 ms 2892 KB Output is correct
10 Correct 100 ms 2816 KB Output is correct
11 Correct 99 ms 2816 KB Output is correct
12 Correct 101 ms 2952 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 1776 KB Output is correct
2 Correct 127 ms 3548 KB Output is correct
3 Correct 134 ms 2808 KB Output is correct
4 Correct 160 ms 2936 KB Output is correct
5 Correct 183 ms 5496 KB Output is correct
6 Correct 207 ms 5672 KB Output is correct
7 Correct 201 ms 5560 KB Output is correct
8 Correct 233 ms 5624 KB Output is correct
9 Correct 205 ms 5496 KB Output is correct
10 Correct 231 ms 5496 KB Output is correct
11 Correct 176 ms 5368 KB Output is correct
12 Correct 286 ms 5496 KB Output is correct