oj.uz

Submission #552714

# Submission time Handle Problem Language Result Execution time Memory
552714 2022-04-23T16:52:10 Z dsyz Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 279 ms 16476 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
/* use "brute force" using point update for divide since
the log2(10^9) <= 32 so it is small enough to divide individually, 
just stop going down when there is v = 0 in the divide function
Also, if K == 1, then dont divide since it will all the way down
as v would not be log() at all so would TLE
* */
ll N,Q,K;
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) >> 1;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll newvalue){
		if(s == e){
			v = newvalue;
		}else{
			if(x >= m + 1) r -> update(x,newvalue);
			else if(x <= m) l -> update(x,newvalue);
			v = l->v + r->v;
		}
	}
	void spray(ll x,ll y){
		if(K == 1) return;
		if(s == e){
			v /= K;
		}else if(s == x && e == y){
			if(v == 0) return;
			l->spray(x,m);
			r->spray(m + 1,y);
			v = l->v + r->v;
		}else{
			if(x >= m + 1) r -> spray(x,y);
			else if(y <= m) l -> spray(x,y);
			else l -> spray(x,m), r -> spray(m + 1,y);
			v = l->v + r->v;
		}
	}
	long long query(ll x,ll y){
		if(s == x && e == y) return v;
		else{
			if(x >= m + 1) return r -> query(x,y);
			else if(y <= m) return l -> query(x,y);
			else return l -> query(x,m) + r -> query(m + 1,y);
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>Q>>K;
	root = new node(0,N + 5);
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		root -> update(i,arr[i]);
	}
	for(ll i = 0;i < Q;i++){
		ll s,t,u;
		cin>>s>>t>>u;
		if(s == 1){
			t--;
			root -> update(t,u);
		}else if(s == 2){
			t--;
			u--;
			root -> spray(t,u);
		}else if(s == 3){
			t--;
			u--;
			cout<<root -> query(t,u)<<'\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 676 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 5 ms 720 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 5 ms 784 KB Output is correct
12 Correct 4 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9060 KB Output is correct
2 Correct 59 ms 6732 KB Output is correct
3 Correct 66 ms 12532 KB Output is correct
4 Correct 83 ms 15880 KB Output is correct
5 Correct 94 ms 16476 KB Output is correct
6 Correct 100 ms 16416 KB Output is correct
7 Correct 97 ms 16420 KB Output is correct
8 Correct 94 ms 16460 KB Output is correct
9 Correct 77 ms 16392 KB Output is correct
10 Correct 76 ms 16284 KB Output is correct
11 Correct 89 ms 16328 KB Output is correct
12 Correct 76 ms 16292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1536 KB Output is correct
2 Correct 24 ms 6484 KB Output is correct
3 Correct 27 ms 6592 KB Output is correct
4 Correct 70 ms 4800 KB Output is correct
5 Correct 134 ms 15000 KB Output is correct
6 Correct 115 ms 15052 KB Output is correct
7 Correct 85 ms 15168 KB Output is correct
8 Correct 114 ms 15040 KB Output is correct
9 Correct 110 ms 14868 KB Output is correct
10 Correct 84 ms 14900 KB Output is correct
11 Correct 79 ms 14892 KB Output is correct
12 Correct 94 ms 14920 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 8804 KB Output is correct
2 Correct 124 ms 9128 KB Output is correct
3 Correct 110 ms 7548 KB Output is correct
4 Correct 144 ms 6420 KB Output is correct
5 Correct 202 ms 16308 KB Output is correct
6 Correct 203 ms 16228 KB Output is correct
7 Correct 185 ms 16320 KB Output is correct
8 Correct 268 ms 16328 KB Output is correct
9 Correct 194 ms 16232 KB Output is correct
10 Correct 235 ms 16200 KB Output is correct
11 Correct 194 ms 16220 KB Output is correct
12 Correct 279 ms 16160 KB Output is correct