Submission #90735

#	Time	Username	Problem	Language	Result	Execution time	Memory
90735		Dat160601	Cake (CEOI14_cake)	C++17	0 / 100	586 ms	96336 KiB

cake

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#pragma GCC optimize("O3")

int n, q, ps, a[250007], x, y, szlef, szrig;
char type;

int read(){
	char p;
	while((p = getchar())){
		if(p < '0' || p > '9') continue;
		break;
	}
	int ret = p - '0';
	while((p = getchar())){
		if(p >= '0' && p <= '9'){
			ret *= 10;
			ret += p - '0';
		}
		else break;
	}
	return ret;
}

struct segtree{
	int it[1000007];

	segtree(){
		memset(it, 0, sizeof(it));
	}

	void update(int k, int l, int r, int pos, int val){
		if(l > pos || r < pos) return;
		if(l == r){
			it[k] = val;
			return;
		}
		int mid = (l + r) >> 1;
		update(k << 1, l, mid, pos, val);
		update(k << 1 | 1, mid + 1, r, pos, val);
		it[k] = max(it[k << 1], it[k << 1 | 1]);
	}

	int get(int k, int l, int r, int L, int R){
		if(l > R || r < L || L > R) return 0;
		if(l >= L && r <= R) return it[k];
		int mid = (l + r) >> 1;
		return max(get(k << 1, l, mid, L, R), get(k << 1 | 1, mid + 1, r, L, R));
	}

	int get_pos(int k, int l, int r, int val){
		int mid = (l + r) >> 1;
		if(it[k] <= val) return r;
		if(l == r) return l - 1;
		if(it[k << 1] > val) return get_pos(k << 1, l, mid, val);
		else return get_pos(k << 1 | 1, mid + 1, r, val);
	}
};

segtree lef = segtree(), rig = segtree();
set < pair <int, int> > st;

int main(){
	#ifdef Dat
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	#endif
	n = read(), ps = read();
	szlef = ps - 1;
	szrig = n - ps;
	for(int i = 1; i <= n; i++){
		a[i] = read();
		if(i < ps) lef.update(1, 1, szlef, szlef - i + 1, a[i]);
		else if(i > ps) rig.update(1, 1, szrig, i - ps, a[i]);
		if(i != ps){
			st.insert(mp(a[i], i));
			while((int)st.size() > 10) st.erase(st.begin());
		}
	}
	int cnt = n;
	//lef.update(1, 1, szlef, szlef, 1e9);
	//rig.update(1, 1, szrig, szrig, 1e9);
	q = read();
	while(q --){
		while((type = getchar())){
			if(type == 'E' || type == 'F') break;
		}
		if(type == 'E'){
			x = read(); y = read();
			if(x == ps) continue;
            cnt = a[(*st.rbegin()).se];
            vector <int> sv;
            for(int i = 1; i < y; i++){
				auto iter = st.rbegin();
				int p = (*iter).se;
				st.erase(*iter);
				sv.pb(p);
				a[p] = cnt + y - i + 1;
				if(p < ps) lef.update(1, 1, szlef, szlef - p + 1, a[p]);
				else rig.update(1, 1, szrig, p - ps, a[p]);
            }
            st.erase(mp(a[x], x));
            a[x] = cnt + 1;
			if(x < ps) lef.update(1, 1, szlef, szlef - x + 1, a[x]);
			else rig.update(1, 1, szrig, x - ps, a[x]);
			st.insert(mp(a[x], x));
			for(int p : sv) st.insert(mp(a[p], p));
			while((int)st.size() > 10) st.erase(st.begin());
		}
		else{
			x = read();
			if(x == ps){
				printf("0\n");
			}
			else if(x < ps){
				int val = lef.get(1, 1, szlef, 1, szlef + 1 - x);
				int add = 1 + rig.get_pos(1, 1, szrig, val);
				add += ps - x - 1;
				printf("%d\n", add);
			}
			else{
				int val = rig.get(1, 1, szrig, 1, x - ps);
				int add = 1 + lef.get_pos(1, 1, szlef, val);
				add += x - ps - 1;
				printf("%d\n", add);
			}
		}
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50