Submission #551730

#	Time	Username	Problem	Language	Result	Execution time	Memory
551730		AugustinasJucas	Cake (CEOI14_cake)	C++14	83.33 / 100	2094 ms	28012 KiB

cake

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct tree {
	const int inf = 1e9;
	vector<int> l, r;
	vector<pair<int, int> > val;
	int n, dbInd = 0;
	void build(int v){
		if(v >= n) {
			l[v] = r[v] = dbInd++;
			val[v] = {0, l[v]};
		}else {
			build(v*2);
			build(v*2+1);
			l[v] = l[v*2];
			r[v] = r[v*2+1];
			val[v] = min(val[v*2], val[v*2+1]);
		}
	}
	tree(int dd) {
		n = dd;
		l.resize(2*n);
		r.resize(2*n);
		val.resize(2*n);
		build(1);
	}
	void change(int v, int L, int R, int x) {
		if(L <= l[v] && r[v] <= R) {
			val[v] = {x, l[v]};
		}else if(R < l[v] || r[v] < L) {
			return ;
		}else {
			change(v*2, L, R, x);
			change(v*2+1, L, R, x);
			val[v] = min(val[v*2], val[v*2+1]);
		}
	}
	pair<int, int> getMin(int v, int L, int R) {
		if(L <= l[v] && r[v] <= R) {
			return val[v];
		}else if(R < l[v] || r[v] < L) {
			return make_pair(inf, inf);
		}else {
			return min(getMin(v*2, L, R), getMin(v*2+1, L, R));
		}
	}
	
};
const int dydis = 250000 + 100;
const int inf = 1e9;
int n;
tree eile(dydis);
set<pair<int, int> > places;
int minimalPlace = 0;
int A;
void enhance(int ind, int place){
	ind--; place--;
	places.erase({eile.getMin(1, ind, ind).first, ind});
	if(place == 0) {
		eile.change(1, ind, ind, minimalPlace-1);
		places.insert({minimalPlace-1, ind});
		minimalPlace--;
	}else {
		auto kur = places.begin();
		int nauja = inf;
		for(int i = 0; i < place; i++) {
			int ind = kur -> second;
			int plc = kur -> first;
			nauja = plc;
			places.erase({plc, ind});
			places.insert({plc-1, ind});
			eile.change(1, ind, ind, plc-1);
			kur++;
		}
		eile.change(1, ind, ind, nauja);
		places.insert({nauja, ind});
		minimalPlace--;
	}
}
int find(int ind) {
	ind--;
	
//	cout << "Findinsiu nuo " << ind << endl;
	if(ind == A) {
	//	cout << "Radau " << 0 << endl;
		return 0;
	}
	

	
	if(ind < A) {
	//	cout << "jis yra kairiau uz A\n";
		auto maz = eile.getMin(1, ind, A-1);
	//	cout << "maziausias yra " << maz.first << ", jo vieta - " << maz.second << endl;
		int l = A+1; int r = n-1; int mid, fd = A;
		while(l <= r) {
			mid = (l + r) / 2;
			if(eile.getMin(1, A+1, mid).first > maz.first) {
				fd = mid;
				l = mid+1;
			}else {
				r = mid-1;
			}
		}
		// Suvalgysiu viska nuo ind+1 iki fd
		return fd - ind;
	}else {
		auto maz = eile.getMin(1, A+1, ind);
		
		int l = 0; int r = A-1; int mid, fd = A;
		while(l <= r) {
			mid = (l + r) / 2;
			if(eile.getMin(1, mid, A-1).first > maz.first) {
				fd = mid;
				r = mid-1;
			}else {
				l = mid+1;
			}
		}
		// Suvalgysiu viska nuo fd iki ind-1
		return ind - fd;
	}
	
	return 0;
}
int main () {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> A; A--;
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		a = n - a;
		eile.change(1, i, i, a);
		places.insert({a, i});
	}
	int q; cin >> q;
	while(q--) {
		char typ;
		int a, b; cin >> typ;
		if(typ == 'E') {
			cin >> a >> b;
			enhance(a, b);
		}else {
			cin >> a;
			int ans = find(a);
			cout << ans << "\n";
		}
	}
	
	return 0;
} 
/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/

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