oj.uz

Submission #860128

# Submission time Handle Problem Language Result Execution time Memory
860128 2023-10-11T17:37:21 Z dsyz Cake (CEOI14_cake) C++17
100 / 100
 1000 ms 41940 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll val){
		if(s == e){
			v = val;
			return;
		}else{
			if(x > m) r -> update(x,val);
			else l -> update(x,val);
			v = max(l->v,r->v);
		}
	}
	ll rmq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmq(x,y);
			else if(y <= m) return l -> rmq(x,y);
			else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
		}
	}
} *root;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,A;
	cin>>N>>A;
	root = new node(1,N);
	ll D[N + 1], pos[10];
	for(ll i = 1;i <= N;i++){
		cin>>D[i];
		root -> update(i,D[i]);
		if(N - D[i] < 10){ //cake i is among top 10 most delicious
			pos[N - D[i]] = i;
		} 
	}
	ll Q;
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		char t;
		cin>>t;
		if(t == 'E'){
			ll x,e;
			cin>>x>>e;
			ll ps = 10;
			for(ll i = 0;i < 10;i++){
				if(pos[i] == x){
					ps = i;
				}
			}
			root -> update(x,root -> rmq(pos[e - 1],pos[e - 1]) + 1);
			while(ps >= e){
				pos[ps] = pos[ps - 1]; //shifting right
				ps--;
			}
			pos[e - 1] = x;
			for(ll i = 0;i < e - 1;i++){
				root -> update(pos[i],root -> rmq(pos[i],pos[i]) + 1);
			}
		}else if(t == 'F'){
			ll x;
			cin>>x;
			if(x == A){
				cout<<0<<'\n';
				continue;
			}else if(x < A){ //left of starting position
				ll mx = root -> rmq(x,A - 1);
				ll high = N + 1;
				ll low = A;
				while(high - low > 1){
					ll mid = (high + low) / 2;
					if(root -> rmq(A + 1,mid) < mx){
						low = mid;
					}else{
						high = mid;
					}
				}
				cout<<low - x<<'\n';
			}else{ //right of starting position
				ll mx = root -> rmq(A + 1,x);
				ll high = A;
				ll low = 0;
				while(high - low > 1){
					ll mid = (high + low) / 2;
					if(root -> rmq(mid,A - 1) < mx){
						high = mid;
					}else{
						low = mid;
					}
				}
				cout<<x - high<<'\n';
			}
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 11 ms 1928 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 5976 KB Output is correct
2 Correct 128 ms 5968 KB Output is correct
3 Correct 150 ms 6100 KB Output is correct
4 Correct 95 ms 6096 KB Output is correct
5 Correct 242 ms 8324 KB Output is correct
6 Correct 230 ms 8532 KB Output is correct
7 Correct 173 ms 8532 KB Output is correct
8 Correct 103 ms 8784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 15544 KB Output is correct
2 Correct 135 ms 15676 KB Output is correct
3 Correct 146 ms 15516 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 269 ms 36800 KB Output is correct
6 Correct 275 ms 36672 KB Output is correct
7 Correct 219 ms 36368 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1116 KB Output is correct
2 Correct 36 ms 1612 KB Output is correct
3 Correct 104 ms 8180 KB Output is correct
4 Correct 102 ms 8228 KB Output is correct
5 Correct 94 ms 2128 KB Output is correct
6 Correct 260 ms 11092 KB Output is correct
7 Correct 135 ms 3908 KB Output is correct
8 Correct 112 ms 16028 KB Output is correct
9 Correct 1000 ms 41940 KB Output is correct
10 Correct 337 ms 5360 KB Output is correct
11 Correct 460 ms 8532 KB Output is correct
12 Correct 897 ms 34504 KB Output is correct
13 Correct 815 ms 41556 KB Output is correct