oj.uz

Submission #697135

# Submission time Handle Problem Language Result Execution time Memory
697135 2023-02-08T14:23:42 Z dsyz Growing Trees (BOI11_grow) C++17
100 / 100
 191 ms 16884 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
	ll s, e, m, val, maxi, lazy;
	node *l, *r;
	node(ll S, ll E){
		s = S, e = E, m = (s+e) >> 1;
		val = 0;
		maxi = 0;
		lazy = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propogate(){
		if(lazy==0) return;
		val += lazy*(e-s+1);
		maxi += lazy;
		if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
			l->lazy += lazy;
			r->lazy += lazy;
		}
		lazy = 0;
	}
	void update(int S, int E, ll V){
		if(s == S && e == E) lazy += V;
		else{
			if(E <= m) l->update(S, E, V);
			else if (m < S) r->update(S, E, V);
			else l->update(S, m, V),r->update(m+1, E, V);
			l->propogate(),r->propogate();
			val = l->val + r->val;
			maxi = max(l -> maxi,r -> maxi);
		}
	}
	ll bsL(ll H){ //leftmost position >= H
		propogate(); //remember to propogate
		if(s == e){
			if(maxi >= H) return s;
			else return 1000000005;
		}
		l -> propogate(), r -> propogate();
		if(l -> maxi >= H){
			return l -> bsL(H);
		}else if(r -> maxi >= H){
			return r -> bsL(H);
		}else{
			return 1000000005;
		}
	}
	ll query(int S, int E){
		propogate(); //remember to propogate
		if(s == S && e == E) return val; 
		else if(E <= m) return l->query(S, E); 
		else if(S >= m+1) return r->query(S, E);
		else return l->query(S, m) + r->query(m+1, E); 
	}
} *root;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	root = new node(0,N - 1);
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	sort(arr,arr + N);
	for(ll i = 0;i < N;i++){
		root -> update(i,i,arr[i]);
	}
	for(ll i = 0;i < M;i++){
		char t;
		cin>>t;
		if(t == 'F'){
			ll c,h;
			cin>>c>>h;
			ll start = root -> bsL(h);
			if(start == 1000000005){
				continue;
			}
			ll endval = root -> query(min(N - 1,start + c - 1),min(N - 1,start + c - 1));
			ll end = -1e18;
			end = root -> bsL(endval);
			end--;
			ll end2 = root -> bsL(endval + 1);
			if(end2 == 1000000005){
				end2 = N - 1;
			}else{
				end2--;
			}
			ll start2 = max(end + 1,end2 - (c - (end - start + 1)) + 1);
			if(start2 == 1000000005){
				continue;
			}
			if(start <= end) root -> update(start,end,1);
			if(start2 <= end2) root -> update(start2,end2,1);
		}else if(t == 'C'){
			ll L,R;
			cin>>L>>R;
			ll start = root -> bsL(L);
			ll end = root -> bsL(R + 1);
			if(end == 1000000005){
				end = N - 1;
			}else{
				end--;
			}
			if(start == 1000000005 || end == 1000000005){
				cout<<0<<'\n';
			}else{
				cout<<end - start + 1<<'\n';
			}
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14848 KB Output is correct
2 Correct 163 ms 14584 KB Output is correct
3 Correct 112 ms 13712 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 580 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 49 ms 1284 KB Output is correct
6 Correct 49 ms 1396 KB Output is correct
7 Correct 5 ms 1108 KB Output is correct
8 Correct 23 ms 1364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1756 KB Output is correct
2 Correct 55 ms 1776 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 33 ms 1612 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1748 KB Output is correct
2 Correct 58 ms 1860 KB Output is correct
3 Correct 11 ms 1460 KB Output is correct
4 Correct 54 ms 1776 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11124 KB Output is correct
2 Correct 158 ms 12276 KB Output is correct
3 Correct 18 ms 3156 KB Output is correct
4 Correct 92 ms 11960 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 12660 KB Output is correct
2 Correct 144 ms 13316 KB Output is correct
3 Correct 111 ms 11732 KB Output is correct
4 Correct 18 ms 3252 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 13584 KB Output is correct
2 Correct 104 ms 14936 KB Output is correct
3 Correct 112 ms 13424 KB Output is correct
4 Correct 17 ms 3156 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 14576 KB Output is correct
2 Correct 140 ms 13008 KB Output is correct
3 Correct 51 ms 16744 KB Output is correct
4 Correct 69 ms 15180 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 14484 KB Output is correct
2 Correct 148 ms 14764 KB Output is correct
3 Correct 191 ms 16468 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 16884 KB Output is correct