oj.uz

Submission #853280

# Submission time Handle Problem Language Result Execution time Memory
853280 2023-09-23T21:17:42 Z epicci23 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 139 ms 9672 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 1e5 + 5;
int fw[N];
void upd(int c,int u){
	for(;c<N;c+=c&-c) fw[c]+=u;
}

int query(int c,int res=0){
	for(;c;c-=c&-c) res+=fw[c];
	return res;
}



void solve(){
	int n,q,k;
	cin >> n >> q >> k;

	int ar[n+1];
	for(int i=1;i<=n;i++) cin >> ar[i];
	for(int i=1;i<=n;i++) upd(i,ar[i]);
    
    set<int> s;
    for(int i=1;i<=n;i++) if(ar[i]>0) s.insert(i);
    
    while(q--){
      int t,l,r;
      cin >> t >> l >> r;
      if(t==1){
      	upd(l,-ar[l]);
      	s.erase(l);
      	ar[l]=r;
      	upd(l,ar[l]);
      	if(ar[l]>0) s.insert(l);
      }
      else if(t==2){
      	if(k==1) continue;
      	auto it=s.lower_bound(l);
      	vector<int> todo;
      	while(it!=s.end() && (*it)<=r){
      		int c = (*it);
      		upd(c,-ar[c]);
      		ar[c]/=k;
      		upd(c,ar[c]);
      		if(ar[c]==0) todo.pb(c);
      		it++;
      	}
        for(int x:todo) s.erase(x);
      }
      else{
      	cout << query(r) - query(l-1) << endl;
      }
    }
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4184 KB Output is correct
2 Correct 35 ms 4444 KB Output is correct
3 Correct 38 ms 7244 KB Output is correct
4 Correct 57 ms 9052 KB Output is correct
5 Correct 61 ms 9544 KB Output is correct
6 Correct 57 ms 9552 KB Output is correct
7 Correct 57 ms 9672 KB Output is correct
8 Correct 70 ms 9548 KB Output is correct
9 Correct 59 ms 9468 KB Output is correct
10 Correct 57 ms 9296 KB Output is correct
11 Correct 55 ms 9296 KB Output is correct
12 Correct 57 ms 9304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 11 ms 2152 KB Output is correct
3 Correct 15 ms 2352 KB Output is correct
4 Correct 30 ms 1560 KB Output is correct
5 Correct 43 ms 4572 KB Output is correct
6 Correct 41 ms 4512 KB Output is correct
7 Correct 43 ms 4980 KB Output is correct
8 Correct 41 ms 5908 KB Output is correct
9 Correct 40 ms 5668 KB Output is correct
10 Correct 42 ms 5956 KB Output is correct
11 Correct 37 ms 5792 KB Output is correct
12 Correct 37 ms 5580 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3760 KB Output is correct
2 Correct 56 ms 3920 KB Output is correct
3 Correct 72 ms 3492 KB Output is correct
4 Correct 63 ms 2644 KB Output is correct
5 Correct 92 ms 6900 KB Output is correct
6 Correct 98 ms 6800 KB Output is correct
7 Correct 85 ms 6992 KB Output is correct
8 Correct 115 ms 6992 KB Output is correct
9 Correct 99 ms 7816 KB Output is correct
10 Correct 108 ms 7368 KB Output is correct
11 Correct 90 ms 7820 KB Output is correct
12 Correct 139 ms 7320 KB Output is correct