oj.uz

Submission #1054438

# Submission time Handle Problem Language Result Execution time Memory
1054438 2024-08-12T09:51:02 Z vako_p Cake (CEOI14_cake) C++14
0 / 100
 35 ms 21340 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;
	assert(q <= 10);
	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 Runtime error 3 ms 8796 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 9308 KB Execution killed with signal 6
2 Runtime error 4 ms 9308 KB Execution killed with signal 6
3 Runtime error 4 ms 9308 KB Execution killed with signal 6
4 Runtime error 4 ms 9308 KB Execution killed with signal 6
5 Runtime error 6 ms 9820 KB Execution killed with signal 6
6 Runtime error 10 ms 9820 KB Execution killed with signal 6
7 Runtime error 6 ms 9820 KB Execution killed with signal 6
8 Runtime error 6 ms 9820 KB Execution killed with signal 6

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 12892 KB Execution killed with signal 6
2 Runtime error 14 ms 12892 KB Execution killed with signal 6
3 Runtime error 14 ms 12892 KB Execution killed with signal 6
4 Runtime error 3 ms 8796 KB Execution killed with signal 6
5 Runtime error 34 ms 21236 KB Execution killed with signal 6
6 Runtime error 35 ms 21276 KB Execution killed with signal 6
7 Runtime error 31 ms 21224 KB Execution killed with signal 6

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9052 KB Execution killed with signal 6
2 Runtime error 3 ms 9052 KB Execution killed with signal 6
3 Runtime error 9 ms 10844 KB Execution killed with signal 6
4 Runtime error 8 ms 10984 KB Execution killed with signal 6
5 Runtime error 3 ms 8796 KB Execution killed with signal 6
6 Runtime error 11 ms 13032 KB Execution killed with signal 6
7 Runtime error 4 ms 9308 KB Execution killed with signal 6
8 Runtime error 15 ms 13036 KB Execution killed with signal 6
9 Runtime error 35 ms 21220 KB Execution killed with signal 6
10 Runtime error 3 ms 8796 KB Execution killed with signal 6
11 Runtime error 5 ms 9820 KB Execution killed with signal 6
12 Runtime error 33 ms 21232 KB Execution killed with signal 6
13 Runtime error 34 ms 21340 KB Execution killed with signal 6