oj.uz

Submission #118957

# Submission time Handle Problem Language Result Execution time Memory
118957 2019-06-20T06:01:44 Z IOrtroiii Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 117 ms 4344 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];
   int 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1024 KB Output is correct
2 Correct 22 ms 1920 KB Output is correct
3 Correct 30 ms 2048 KB Output is correct
4 Correct 91 ms 2296 KB Output is correct
5 Correct 112 ms 4344 KB Output is correct
6 Correct 107 ms 4344 KB Output is correct
7 Correct 106 ms 4344 KB Output is correct
8 Correct 113 ms 4344 KB Output is correct
9 Correct 101 ms 4088 KB Output is correct
10 Correct 103 ms 4220 KB Output is correct
11 Correct 104 ms 4280 KB Output is correct
12 Correct 100 ms 4216 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -