oj.uz

Submission #1054383

# Submission time Handle Problem Language Result Execution time Memory
1054383 2024-08-12T09:20:38 Z vako_p Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 10836 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);
	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];
		}
	}
//5 3
//5 1 2 4 3
//1
//F 2
	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);
//			cout << "--> ";
//			for(int i = 0; i < n; i++) cout << a[i] << ' ';
//			cout << '\n';
		}
	}
}
//5 3
//5 1 2 4 3
//2
//E 2 1
//F 2

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 189 ms 4700 KB Output isn't correct
2 Incorrect 188 ms 4700 KB Output isn't correct
3 Incorrect 210 ms 4696 KB Output isn't correct
4 Correct 198 ms 4816 KB Output is correct
5 Incorrect 215 ms 4952 KB Output isn't correct
6 Incorrect 210 ms 4956 KB Output isn't correct
7 Incorrect 219 ms 4952 KB Output isn't correct
8 Correct 209 ms 5072 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 6492 KB Time limit exceeded
2 Execution timed out 2095 ms 6620 KB Time limit exceeded
3 Execution timed out 2075 ms 6492 KB Time limit exceeded
4 Incorrect 1 ms 4440 KB Output isn't correct
5 Execution timed out 2095 ms 10736 KB Time limit exceeded
6 Execution timed out 2100 ms 10588 KB Time limit exceeded
7 Execution timed out 2021 ms 10716 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 4656 KB Output isn't correct
2 Incorrect 201 ms 4696 KB Output isn't correct
3 Execution timed out 2075 ms 5716 KB Time limit exceeded
4 Execution timed out 2045 ms 5872 KB Time limit exceeded
5 Incorrect 209 ms 4688 KB Output isn't correct
6 Execution timed out 2045 ms 6672 KB Time limit exceeded
7 Incorrect 1162 ms 5144 KB Output isn't correct
8 Incorrect 339 ms 6616 KB Output isn't correct
9 Execution timed out 2081 ms 10728 KB Time limit exceeded
10 Incorrect 743 ms 5444 KB Output isn't correct
11 Execution timed out 2052 ms 5436 KB Time limit exceeded
12 Execution timed out 2069 ms 10836 KB Time limit exceeded
13 Execution timed out 2066 ms 10588 KB Time limit exceeded