oj.uz

Submission #1054409

# Submission time Handle Problem Language Result Execution time Memory
1054409 2024-08-12T09:41:13 Z vako_p Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 12120 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back

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

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(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;
		s.set(a[idx], idx);
		return;
	}
	a[idx] = last[val];
	ll idx2 = idx1[val];
	idx1[val] = idx; 
	s.set(a[idx], idx);
	if(idx2 != idx) f(idx2, 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];
		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;
			cin >> idx >> val;
			idx--;
			f(idx, val);
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 7724 KB Output isn't correct
2 Incorrect 185 ms 7140 KB Output isn't correct
3 Incorrect 214 ms 7252 KB Output isn't correct
4 Correct 225 ms 7508 KB Output is correct
5 Incorrect 220 ms 8020 KB Output isn't correct
6 Incorrect 209 ms 8132 KB Output isn't correct
7 Incorrect 244 ms 8072 KB Output isn't correct
8 Correct 208 ms 8272 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 7316 KB Time limit exceeded
2 Execution timed out 2076 ms 7196 KB Time limit exceeded
3 Execution timed out 2033 ms 7276 KB Time limit exceeded
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Execution timed out 2089 ms 11944 KB Time limit exceeded
6 Execution timed out 2064 ms 12116 KB Time limit exceeded
7 Execution timed out 2060 ms 12028 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 5012 KB Output isn't correct
2 Incorrect 157 ms 5100 KB Output isn't correct
3 Execution timed out 2009 ms 6224 KB Time limit exceeded
4 Execution timed out 2037 ms 6316 KB Time limit exceeded
5 Incorrect 225 ms 5580 KB Output isn't correct
6 Execution timed out 2071 ms 7448 KB Time limit exceeded
7 Incorrect 1176 ms 6584 KB Output isn't correct
8 Incorrect 340 ms 8020 KB Output isn't correct
9 Execution timed out 2068 ms 12120 KB Time limit exceeded
10 Incorrect 710 ms 8016 KB Output isn't correct
11 Execution timed out 2058 ms 6632 KB Time limit exceeded
12 Execution timed out 2039 ms 11408 KB Time limit exceeded
13 Execution timed out 2029 ms 11344 KB Time limit exceeded