oj.uz

Submission #124796

# Submission time Handle Problem Language Result Execution time Memory
124796 2019-07-04T02:06:39 Z iqvocuc Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 543 ms 5732 KB 
#include<bits/stdc++.h>
using namespace std;
int n, q, k;
long long a[100100];
long long st[200200];
void build(int id, int l, int r) {
   if (l == r) {
      st[id] =  a[l];
      return;
   }
   int mid=(l+r)/2;
   build(id*2,l,mid);
   build(id*2+1, mid + 1, r);
   st[id] = st[id*2] + st[id *2 +1 ];
}
void truyvan2(int id, int l, int r, int L, int R) {
   if (st[id] == 0 || k == 1) return;
   if (l == r) {
      st[id] /= k;
      return;
   }
   int mid=(l+r)/2;
 if(L<=mid)  truyvan2(id*2, l, mid, L, R);
  if(R>mid)  truyvan2(id*2+1, mid + 1, r, L, R);
   st[id] = st[id*2] + st[id*2+1];
}
void truyvan1(int id, int l, int r, int L, int R) {
   if (l == r) {
      st[id] = R;
      return;
   }
   int mid=(l+r)/2;
   if (L <= mid) truyvan1(id*2, l, mid, L, R);
   else truyvan1(id*2+1, mid + 1, r, L, R);
   st[id] = st[id*2] + st[id*2+1];
}
long long truyvan3(int id, int l, int r, int u, int v) {
   if (u <= l && r <= v) return st[id];
   long long tong = 0;
   int mid=(l+r)/2;
   if (u <= mid) tong += truyvan3(id*2, l, mid, u, v);
   if (mid < v) tong += truyvan3(id*2+1, mid + 1, r, u, v);
   return tong;
}
int main (){
   cin >> n >> q >> k;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
   }
   build(1, 1, n);
   while (q--) {
      int query;
      cin >> query;
      if (query == 1) {
         int x, y;
         cin >> x>> y;
         truyvan1(1, 1, n, x, y);
      } else if (query == 2) {
         int xx, yy;
         cin >> xx >> yy;
         truyvan2(1, 1, n, xx, yy);
      } else {
         int xx, yy;
         cin >> xx >> yy;
         cout << truyvan3(1, 1, n, xx,yy) << endl;
      }
   }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 14 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 13 ms 504 KB Output is correct
8 Correct 13 ms 504 KB Output is correct
9 Correct 14 ms 504 KB Output is correct
10 Correct 13 ms 504 KB Output is correct
11 Correct 13 ms 568 KB Output is correct
12 Correct 13 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 4192 KB Output is correct
2 Correct 244 ms 3704 KB Output is correct
3 Correct 214 ms 4496 KB Output is correct
4 Correct 272 ms 5232 KB Output is correct
5 Correct 327 ms 5732 KB Output is correct
6 Correct 336 ms 5568 KB Output is correct
7 Correct 328 ms 5624 KB Output is correct
8 Correct 328 ms 5600 KB Output is correct
9 Correct 317 ms 5472 KB Output is correct
10 Correct 321 ms 5636 KB Output is correct
11 Correct 319 ms 5468 KB Output is correct
12 Correct 312 ms 5632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1144 KB Output is correct
2 Correct 51 ms 2040 KB Output is correct
3 Correct 74 ms 2040 KB Output is correct
4 Correct 239 ms 2308 KB Output is correct
5 Correct 287 ms 4216 KB Output is correct
6 Correct 273 ms 4232 KB Output is correct
7 Correct 268 ms 4268 KB Output is correct
8 Correct 274 ms 4472 KB Output is correct
9 Correct 261 ms 4252 KB Output is correct
10 Correct 256 ms 4104 KB Output is correct
11 Correct 258 ms 4112 KB Output is correct
12 Correct 270 ms 3980 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 3632 KB Output is correct
2 Correct 299 ms 3648 KB Output is correct
3 Correct 253 ms 3036 KB Output is correct
4 Correct 341 ms 3192 KB Output is correct
5 Correct 415 ms 5444 KB Output is correct
6 Correct 445 ms 5452 KB Output is correct
7 Correct 407 ms 5496 KB Output is correct
8 Correct 485 ms 5496 KB Output is correct
9 Correct 478 ms 5424 KB Output is correct
10 Correct 477 ms 5392 KB Output is correct
11 Correct 417 ms 5368 KB Output is correct
12 Correct 543 ms 5516 KB Output is correct