Submission #551754

#	Time	Username	Problem	Language	Result	Execution time	Memory
551754		AugustinasJucas	Cake (CEOI14_cake)	C++14	100 / 100	1645 ms	20492 KiB

cake

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct tree {
	const int inf = 1e9;
	vector<int> l, r;
	vector<int> val;
	int n, dbInd = 0;
	void build(int v){
		if(v >= n) {
			l[v] = r[v] = dbInd++;
		}else {
			build(v*2);
			build(v*2+1);
			l[v] = l[v*2];
			r[v] = r[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;
		}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]);
		}
	}
	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 inf;
		}else {
			return min(getMin(v*2, L, R), getMin(v*2+1, L, R));
		}
	}
	
	int rightmost(int v, int L, int R, int x) {
		// randa desiniausia 'i' is [L; R], kad min(L; a[i]) >= x
	//	cout << "esu node [" << l[v] << "; " << r[v] << "]\n";
		if(L <= l[v] && r[v] <= R) {
			if(l[v] == r[v]) {
				if(val[v] >= x) return l[v];
				else return -inf;
			}
			
			if(val[v*2] >= x) {
				return max(r[v*2], rightmost(v*2+1, L, R, x));
			}else {
				return rightmost(v*2, L, R, x);
			}
			
		}else if(R < l[v] || r[v] < L) {
			return -inf;
		}else {
			if(r[v*2] < L) return rightmost(v*2+1, L, R, x);
			
			int kaireje = rightmost(v*2, L, R, x);
			if(kaireje != r[v*2]) {
				return kaireje;
			}else {
				return max(r[v*2], rightmost(v*2+1, L, R, x));
			}
			
		}
	}
	int leftmost(int v, int L, int R, int x) {
		// randa kairiausia 'i' is [L; R], kad min(a[i]; R) >= x
	//	cout << "esu node [" << l[v] << "; " << r[v] << "]\n";
		if(L <= l[v] && r[v] <= R) {
			if(l[v] == r[v]) {
				if(val[v] >= x) return l[v];
				else return inf;
			}
			
			if(val[v*2+1] >= x) {
				return min(l[v*2+1], leftmost(v*2, L, R, x));
			}else {
				return leftmost(v*2+1, L, R, x);
			}
			
		}else if(R < l[v] || r[v] < L) {
			return inf;
		}else {
			if(l[v*2+1] > R) return leftmost(v*2, L, R, x);
			
			int desineje = leftmost(v*2+1, L, R, x);
			if(desineje != l[v*2+1]) {
				return desineje;
			}else {
				return min(l[v*2+1], leftmost(v*2, L, R, x));
			}
			
		}
	}
	
};
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), 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) > maz) {
				fd = mid;
				l = mid+1;
			}else {
				r = mid-1;
			}
		}*/
		fd = max(A, eile.rightmost(1, A+1, n-1, maz));
	/*	cout << "vietos atrodo taip: ";
		for(int i = 0; i < n; i++) {
			cout << eile.getMin(1, i, i) << " ";
		}
		cout << ". Ieskosiu intervale [" << A+1 << "; " << n-1 << "] desiniausio, kad priesdelis butu didesnis uz " << maz << endl;
		cout << "siaip fd = " << fd << ", bet man siulo " << siulo << endl << endl;
		*/
		// 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) > maz) {
				fd = mid;
				r = mid-1;
			}else {
				l = mid+1;
			}
		}*/
		fd = min(A, eile.leftmost(1, 0, A-1, maz));
		// 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
*/

Compilation message (stderr)

cake.cpp: In function 'int find(int)':
cake.cpp:153:7: warning: unused variable 'l' [-Wunused-variable]
  153 |   int l = A+1; int r = n-1; int mid, fd = A;
      |       ^
cake.cpp:153:20: warning: unused variable 'r' [-Wunused-variable]
  153 |   int l = A+1; int r = n-1; int mid, fd = A;
      |                    ^
cake.cpp:153:33: warning: unused variable 'mid' [-Wunused-variable]
  153 |   int l = A+1; int r = n-1; int mid, fd = A;
      |                                 ^~~
cake.cpp:177:7: warning: unused variable 'l' [-Wunused-variable]
  177 |   int l = 0; int r = A-1; int mid, fd = A;
      |       ^
cake.cpp:177:18: warning: unused variable 'r' [-Wunused-variable]
  177 |   int l = 0; int r = A-1; int mid, fd = A;
      |                  ^
cake.cpp:177:31: warning: unused variable 'mid' [-Wunused-variable]
  177 |   int l = 0; int r = A-1; int mid, fd = A;
      |                               ^~~

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