oj.uz

Submission #1054380

# Submission time Handle Problem Language Result Execution time Memory
1054380 2024-08-12T09:18:43 Z vako_p Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 16868 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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(10LL, 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 191 ms 8392 KB Output isn't correct
2 Incorrect 179 ms 9040 KB Output isn't correct
3 Incorrect 196 ms 8788 KB Output isn't correct
4 Correct 205 ms 9432 KB Output is correct
5 Incorrect 221 ms 8528 KB Output isn't correct
6 Incorrect 200 ms 9044 KB Output isn't correct
7 Incorrect 225 ms 8784 KB Output isn't correct
8 Correct 204 ms 9040 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 9692 KB Time limit exceeded
2 Execution timed out 2041 ms 9556 KB Time limit exceeded
3 Execution timed out 2047 ms 9556 KB Time limit exceeded
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Execution timed out 2093 ms 16868 KB Time limit exceeded
6 Execution timed out 2040 ms 16724 KB Time limit exceeded
7 Execution timed out 2039 ms 16720 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 5116 KB Output isn't correct
2 Incorrect 148 ms 5200 KB Output isn't correct
3 Correct 1985 ms 7764 KB Output is correct
4 Execution timed out 2043 ms 7556 KB Time limit exceeded
5 Incorrect 207 ms 5976 KB Output isn't correct
6 Execution timed out 2072 ms 9808 KB Time limit exceeded
7 Incorrect 1127 ms 6996 KB Output isn't correct
8 Incorrect 345 ms 10572 KB Output isn't correct
9 Execution timed out 2068 ms 16724 KB Time limit exceeded
10 Incorrect 721 ms 9120 KB Output isn't correct
11 Execution timed out 2043 ms 7600 KB Time limit exceeded
12 Execution timed out 2062 ms 16468 KB Time limit exceeded
13 Execution timed out 2059 ms 16600 KB Time limit exceeded