oj.uz

Submission #1054506

# Submission time Handle Problem Language Result Execution time Memory
1054506 2024-08-12T10:19:57 Z vako_p Cake (CEOI14_cake) C++14
100 / 100
 282 ms 17212 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back

const int mxN = 1e6;
ll n,a[2 * mxN],idx1[2 * mxN],q,st,mx,last[mxN],idx2[2 * mxN],mx1;

struct segtree{
	vector<pair<ll,ll>> v;
	ll sz = 1;	
	
	void init(){
		while(sz < n) sz *= 2;
		v.assign(2 * sz, {0LL, 0LL});
	}
	
	void set(ll val, ll i, ll x, ll l, ll r){
		if(r - l == 1){
			v[x] = {val, i};
			return;
		}
		ll mid = l + (r - l) / 2;
		if(i < mid) set(val, i, 2 * x + 1, l, mid);
		else set(val, i, 2 * x + 2, mid, r);
		v[x] = max(v[2 * x + 1], v[2 * x + 2]);
	}
	
	void set(ll val, ll i){
		set(val, i, 0, 0, sz);
	}
	
	pair<ll,ll> find(ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return {0, 0};
		if(lx >= l and rx <= r) return v[x];
		ll mid = lx + (rx - lx) / 2;
		return max(find(l, r, 2 * x + 1, lx, mid), find(l, r, 2 * x + 2, mid, rx));
	}
	
	pair<ll,ll> find(ll l, ll r){
		return find(l, r, 0, 0, sz);
	}
	
	pair<ll,ll> find1(ll val, ll l, ll r, ll op, ll x, ll lx, ll rx){
		if(v[x].first <= val) return {-1, -1};
		if(lx >= r or rx <= l) return {-1, -1};
		if(rx - lx == 1){
			if(v[x].first > val) return v[x];
			return {-1, -1};
		}
		ll mid = lx + (rx - lx) / 2;
		pair<ll,ll> ans = find1(val, l, r, op, 2 * x + 1 + op, ((!op) ? (lx) : (mid)), ((!op) ? (mid) : (rx)));
		if(ans.first > val) return ans;
		ans = find1(val, l, r, op, 2 * x + 2 - op, ((!op) ? (mid) : (lx)), ((!op) ? (rx) : (mid)));
		if(ans.first > val) return ans;
		return {-1, -1};
	}
	
	pair<ll,ll> find1(ll val, ll l, ll r, ll op){
		return find1(val, l, r, op, 0, 0, sz);
	}
};
segtree s;

void f(ll idx, ll val){
	if(val == mx){
		a[idx] = ++last[mx];
		idx1[mx] = idx;
		idx2[idx] = mx;
		s.set(a[idx], idx);
		return;
	}
	if(mx1 == -1) mx1 = min(mx, idx2[idx]);
	a[idx] = last[val];
	ll idx3 = idx1[val];
	idx1[val] = idx; 
	idx2[idx] = val;
	s.set(a[idx], idx);
	if(mx1 == val) return;
	if(idx3 != idx) f(idx3, val + 1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> st;
	mx = min(10, n);
	st--;
	s.init();
	for(int i = 0; i < n; i++){
		cin >> a[i];
		idx2[i] = n - a[i] + 1;
		if(n - a[i] <= mx - 2){
			s.set(a[i] + mxN, i);
			last[n - a[i] + 1] = a[i] + mxN;
			idx1[n - a[i] + 1] = i;
			a[i] += mxN; 
		}
		else s.set(a[i], i);
		if(n - a[i] == mx - 1){
			idx1[n - a[i] + 1] = i;
			last[mx] = a[i];
		}
	}
	cin >> q;
	while(q--){
		char op;
		cin >> op;
		if(op == 'F'){
			ll idx;
			cin >> idx;
			idx--;
			if(idx == st){
				cout << 0 << '\n';
				continue;
			}
			pair<ll,ll> x,x1;
			if(idx < st){
				x = s.find(idx, st);
				x1 = s.find1(x.first, st + 1, n, 0);
				if(x1.first <= x.first) cout << n - 1 - idx << '\n';
				else cout << x1.second - idx - 1 << '\n';
			}
			else{
				x = s.find(st + 1, idx + 1); 
				x1 = s.find1(x.first, 0, st, 1);
				if(x1.first <= x.first) cout << idx << '\n';
				else cout << idx - x1.second - 1 << '\n';
			}	
		}
		else{
			ll idx,val;
			mx1 = -1;
			cin >> idx >> val;
			idx--;
			f(idx, val);
//			for(int i = 0; i < n; i++) cout << a[i] << ' ';
//			cout << '\n' << "--> ";
//			for(int i = 0; i < n; i++) cout << s.find(i, i + 1).first << ' ';
//			cout << '\n';
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 5 ms 6924 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 6748 KB Output is correct
2 Correct 74 ms 6748 KB Output is correct
3 Correct 166 ms 6748 KB Output is correct
4 Correct 76 ms 6744 KB Output is correct
5 Correct 148 ms 7000 KB Output is correct
6 Correct 112 ms 7004 KB Output is correct
7 Correct 129 ms 7004 KB Output is correct
8 Correct 78 ms 7004 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11808 KB Output is correct
2 Correct 41 ms 11604 KB Output is correct
3 Correct 37 ms 11604 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 63 ms 14040 KB Output is correct
6 Correct 60 ms 13904 KB Output is correct
7 Correct 46 ms 13648 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6744 KB Output is correct
2 Correct 32 ms 6748 KB Output is correct
3 Correct 44 ms 9924 KB Output is correct
4 Correct 41 ms 10064 KB Output is correct
5 Correct 53 ms 6736 KB Output is correct
6 Correct 110 ms 11712 KB Output is correct
7 Correct 88 ms 7252 KB Output is correct
8 Correct 86 ms 10884 KB Output is correct
9 Correct 282 ms 16656 KB Output is correct
10 Correct 166 ms 7620 KB Output is correct
11 Correct 187 ms 9924 KB Output is correct
12 Correct 267 ms 17128 KB Output is correct
13 Correct 212 ms 17212 KB Output is correct