oj.uz

Submission #965472

# Submission time Handle Problem Language Result Execution time Memory
965472 2024-04-18T17:07:20 Z Trisanu_Das Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 211 ms 10312 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int n, q, k, c[200005], BIT[100005];
set<int> s;
 
void upd(int idx, int val){
  for(; idx <= n; idx += (idx & -idx)) BIT[idx] += val;
}
 
int qry(int idx){
  int ans = 0;
  for(; idx; idx -= (idx & -idx)) ans += BIT[idx];
  return ans;
}
 
signed main(){
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  cin >> n >> q >> k;
  for(int i = 1; i <= n; i++){
    cin >> c[i];
    upd(i, c[i]);
    if(c[i]) s.insert(i);
  }
  while(q--){
    int op; cin >> op;
    if(op == 1){
      int idx, val; cin >> idx >> val;
      upd(idx, val - c[idx]);
      c[idx] = val;
      if(val) s.insert(idx);
    }else if(op == 2){
      int l, r; cin >> l >> r;
      if(k == 1) continue;
      vector<int> del;
      for(auto it = s.begin(); it != s.end(); it++){
        int x = *it;
        if(l <= x && x <= r) {
          upd(x, c[x] / k - c[x]);
          c[x] /= k;
          if(!c[x]) del.push_back(x);
        }
      }
      for(int x : del) s.erase(x);
    }else{
      int l, r; cin >> l >> r;
      cout << qry(r) - qry(l - 1) << '\n';
    }
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2648 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 5 ms 2652 KB Output is correct
10 Correct 4 ms 2652 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7260 KB Output is correct
2 Correct 30 ms 6236 KB Output is correct
3 Correct 35 ms 8016 KB Output is correct
4 Correct 46 ms 9812 KB Output is correct
5 Correct 56 ms 10068 KB Output is correct
6 Correct 70 ms 10312 KB Output is correct
7 Correct 51 ms 10064 KB Output is correct
8 Correct 51 ms 10128 KB Output is correct
9 Correct 58 ms 10052 KB Output is correct
10 Correct 65 ms 10036 KB Output is correct
11 Correct 49 ms 10064 KB Output is correct
12 Correct 51 ms 9916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3164 KB Output is correct
2 Correct 12 ms 3932 KB Output is correct
3 Correct 14 ms 4184 KB Output is correct
4 Correct 27 ms 4444 KB Output is correct
5 Correct 43 ms 6620 KB Output is correct
6 Correct 43 ms 6480 KB Output is correct
7 Correct 37 ms 6748 KB Output is correct
8 Correct 49 ms 6564 KB Output is correct
9 Correct 37 ms 6460 KB Output is correct
10 Correct 35 ms 6468 KB Output is correct
11 Correct 35 ms 6476 KB Output is correct
12 Correct 37 ms 6344 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 6784 KB Output is correct
2 Correct 82 ms 6948 KB Output is correct
3 Correct 128 ms 6112 KB Output is correct
4 Correct 94 ms 5968 KB Output is correct
5 Correct 146 ms 10120 KB Output is correct
6 Correct 159 ms 10064 KB Output is correct
7 Correct 129 ms 10068 KB Output is correct
8 Correct 211 ms 10148 KB Output is correct
9 Correct 85 ms 10064 KB Output is correct
10 Correct 103 ms 9968 KB Output is correct
11 Correct 78 ms 10116 KB Output is correct
12 Correct 109 ms 10116 KB Output is correct