oj.uz

Submission #853279

# Submission time Handle Problem Language Result Execution time Memory
853279 2023-09-23T21:16:28 Z epicci23 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 9492 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){
      	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 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 4 ms 748 KB Output is correct
12 Correct 4 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 5432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 988 KB Output is correct
2 Correct 11 ms 2396 KB Output is correct
3 Correct 14 ms 2652 KB Output is correct
4 Correct 28 ms 2580 KB Output is correct
5 Correct 40 ms 5920 KB Output is correct
6 Correct 43 ms 5716 KB Output is correct
7 Execution timed out 5058 ms 5276 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5280 KB Output is correct
2 Correct 58 ms 5460 KB Output is correct
3 Correct 75 ms 4572 KB Output is correct
4 Correct 64 ms 4588 KB Output is correct
5 Correct 97 ms 9492 KB Output is correct
6 Correct 102 ms 9364 KB Output is correct
7 Correct 91 ms 9352 KB Output is correct
8 Correct 119 ms 9480 KB Output is correct
9 Correct 102 ms 9380 KB Output is correct
10 Correct 112 ms 9240 KB Output is correct
11 Correct 87 ms 9384 KB Output is correct
12 Correct 137 ms 9340 KB Output is correct