oj.uz

Submission #529170

# Submission time Handle Problem Language Result Execution time Memory
529170 2022-02-22T10:48:02 Z AdamGS Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1398 ms 9716 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
ll tr[4*LIM], N=1;
set<int>S;
void upd(int v, ll x) {
  v+=N;
  tr[v]=x;
  v/=2;
  while(v) {
    tr[v]=tr[2*v]+tr[2*v+1];
    v/=2;
  }
}
ll cnt(int l, int r) {
  l+=N; r+=N;
  ll ans=tr[l];
  if(l!=r) ans+=tr[r];
  while(l/2!=r/2) {
    if(l%2==0) ans+=tr[l+1];
    if(r%2==1) ans+=tr[r-1];
    l/=2; r/=2;
  }
  return ans;
}

int main() {
  int n, q, k;
  cin >> n >> q >> k;
  while(N<n) N*=2;
  rep(i, n) {
    cin >> tr[N+i];
    if(tr[N+i]) S.insert(i);
  }
  S.insert(n);
  for(int i=N-1; i; --i) tr[i]=tr[2*i]+tr[2*i+1];
  while(q--) {
    int t, a, b;
    cin >> t >> a >> b;
    if(t==1) {
      --a;
      auto it=S.lower_bound(a);
      if((*it)==a) S.erase(a);
      upd(a, b);
      if(b) S.insert(a);
    } else if(t==2) {
      --a; --b;
      if(k>1) {
        while(a<=b) {
          auto it=S.lower_bound(a);
          a=*it;
          if(a>b) break;
          S.erase(a);
          upd(a, tr[N+a]/k);
          if(tr[N+a]) S.insert(a);
          ++a;
        }
      }
    } else {
      --a; --b;
      cout << cnt(a, b) << '\n';
    }
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 15 ms 504 KB Output is correct
5 Correct 17 ms 460 KB Output is correct
6 Correct 12 ms 460 KB Output is correct
7 Correct 14 ms 460 KB Output is correct
8 Correct 16 ms 444 KB Output is correct
9 Correct 21 ms 460 KB Output is correct
10 Correct 15 ms 564 KB Output is correct
11 Correct 14 ms 460 KB Output is correct
12 Correct 15 ms 572 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 5800 KB Output is correct
2 Correct 144 ms 4660 KB Output is correct
3 Correct 132 ms 7496 KB Output is correct
4 Correct 168 ms 9256 KB Output is correct
5 Correct 200 ms 9692 KB Output is correct
6 Correct 217 ms 9668 KB Output is correct
7 Correct 191 ms 9716 KB Output is correct
8 Correct 187 ms 9696 KB Output is correct
9 Correct 201 ms 9652 KB Output is correct
10 Correct 193 ms 9584 KB Output is correct
11 Correct 183 ms 9584 KB Output is correct
12 Correct 222 ms 9616 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1016 KB Output is correct
2 Correct 29 ms 2500 KB Output is correct
3 Correct 44 ms 2568 KB Output is correct
4 Correct 148 ms 2632 KB Output is correct
5 Correct 141 ms 5828 KB Output is correct
6 Correct 159 ms 5816 KB Output is correct
7 Correct 160 ms 5968 KB Output is correct
8 Correct 138 ms 5824 KB Output is correct
9 Correct 133 ms 5712 KB Output is correct
10 Correct 147 ms 5744 KB Output is correct
11 Correct 131 ms 5700 KB Output is correct
12 Correct 133 ms 5732 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 5288 KB Output is correct
2 Correct 313 ms 5496 KB Output is correct
3 Correct 619 ms 4444 KB Output is correct
4 Correct 384 ms 4184 KB Output is correct
5 Correct 624 ms 9456 KB Output is correct
6 Correct 761 ms 9468 KB Output is correct
7 Correct 586 ms 9400 KB Output is correct
8 Correct 1105 ms 9420 KB Output is correct
9 Correct 833 ms 9412 KB Output is correct
10 Correct 971 ms 9392 KB Output is correct
11 Correct 593 ms 9348 KB Output is correct
12 Correct 1398 ms 9432 KB Output is correct