oj.uz

Submission #236161

# Submission time Handle Problem Language Result Execution time Memory
236161 2020-05-31T10:26:50 Z kshitij_sodani Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1416 ms 11256 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,q,k;
llo aa,bb,cc;
llo it[100001];
llo tree[100001];
void u(llo i,llo j){
	while(i<=100000){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo s(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>q>>k;
	set<pair<llo,llo>> ss;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		u(i+1,it[i]);
		ss.insert({i,it[i]});
	}

	for(llo i=0;i<q;i++){
		cin>>aa>>bb>>cc;
		if(aa==1){
			if(it[bb-1]>0){
				ss.erase({bb-1,it[bb-1]});
			}
			u(bb,-it[bb-1]);
			it[bb-1]=cc;

			u(bb,cc);
			if(cc>0){
				ss.insert({bb-1,it[bb-1]});
			}
		}
		else if(aa==2){
			if(k>1){
				auto j=ss.lower_bound({bb-1,0});
				while((*j).a<cc and j!=ss.end()){
					llo ind=(*j).a;
					u(ind+1,-it[ind]);
					pair<llo,llo> kk=*j;
					ss.erase(j);
					it[ind]=it[ind]/k;
					if(it[ind]>0){
						u(ind+1,it[ind]);
						ss.insert({ind,it[ind]});
					}
					j=ss.upper_bound(kk);
				}
			}
		}
		else{
			cout<<s(cc)-s(bb-1)<<endl;

		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 9 ms 512 KB Output is correct
4 Correct 22 ms 640 KB Output is correct
5 Correct 21 ms 768 KB Output is correct
6 Correct 16 ms 640 KB Output is correct
7 Correct 19 ms 640 KB Output is correct
8 Correct 19 ms 640 KB Output is correct
9 Correct 24 ms 640 KB Output is correct
10 Correct 19 ms 768 KB Output is correct
11 Correct 19 ms 640 KB Output is correct
12 Correct 19 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6520 KB Output is correct
2 Correct 132 ms 5016 KB Output is correct
3 Correct 117 ms 8312 KB Output is correct
4 Correct 154 ms 10616 KB Output is correct
5 Correct 178 ms 11128 KB Output is correct
6 Correct 180 ms 11256 KB Output is correct
7 Correct 183 ms 11128 KB Output is correct
8 Correct 175 ms 11128 KB Output is correct
9 Correct 171 ms 11000 KB Output is correct
10 Correct 184 ms 11000 KB Output is correct
11 Correct 182 ms 11000 KB Output is correct
12 Correct 179 ms 11128 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1400 KB Output is correct
2 Correct 39 ms 4096 KB Output is correct
3 Correct 49 ms 4224 KB Output is correct
4 Correct 111 ms 3608 KB Output is correct
5 Correct 145 ms 9720 KB Output is correct
6 Correct 149 ms 9848 KB Output is correct
7 Correct 162 ms 9720 KB Output is correct
8 Correct 152 ms 9848 KB Output is correct
9 Correct 146 ms 9592 KB Output is correct
10 Correct 144 ms 9584 KB Output is correct
11 Correct 146 ms 9592 KB Output is correct
12 Correct 144 ms 9584 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 6136 KB Output is correct
2 Correct 303 ms 6424 KB Output is correct
3 Correct 606 ms 5216 KB Output is correct
4 Correct 367 ms 4856 KB Output is correct
5 Correct 536 ms 11000 KB Output is correct
6 Correct 683 ms 10976 KB Output is correct
7 Correct 516 ms 11128 KB Output is correct
8 Correct 939 ms 11000 KB Output is correct
9 Correct 775 ms 10872 KB Output is correct
10 Correct 949 ms 10872 KB Output is correct
11 Correct 586 ms 10896 KB Output is correct
12 Correct 1416 ms 10976 KB Output is correct