oj.uz

Submission #551733

# Submission time Handle Problem Language Result Execution time Memory
551733 2022-04-21T11:55:01 Z AugustinasJucas Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 19540 KB 
#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));
		}
	}
	
};
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;
			}
		}
		// 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;
			}
		}
		// 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6100 KB Output is correct
2 Correct 11 ms 6196 KB Output is correct
3 Correct 5 ms 6100 KB Output is correct
4 Correct 20 ms 6272 KB Output is correct
5 Correct 36 ms 6740 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 6624 KB Output is correct
2 Correct 442 ms 6632 KB Output is correct
3 Correct 647 ms 6660 KB Output is correct
4 Correct 332 ms 6664 KB Output is correct
5 Correct 824 ms 7348 KB Output is correct
6 Correct 668 ms 7380 KB Output is correct
7 Correct 559 ms 7468 KB Output is correct
8 Correct 365 ms 7360 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 11404 KB Output is correct
2 Correct 347 ms 11276 KB Output is correct
3 Correct 336 ms 11348 KB Output is correct
4 Correct 5 ms 6100 KB Output is correct
5 Correct 567 ms 18600 KB Output is correct
6 Correct 443 ms 18700 KB Output is correct
7 Correct 376 ms 18416 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6412 KB Output is correct
2 Correct 107 ms 6448 KB Output is correct
3 Correct 256 ms 8672 KB Output is correct
4 Correct 278 ms 8732 KB Output is correct
5 Correct 361 ms 6540 KB Output is correct
6 Correct 494 ms 9820 KB Output is correct
7 Correct 374 ms 7272 KB Output is correct
8 Correct 390 ms 11024 KB Output is correct
9 Execution timed out 2063 ms 19444 KB Time limit exceeded
10 Correct 1118 ms 7460 KB Output is correct
11 Correct 1526 ms 8504 KB Output is correct
12 Execution timed out 2053 ms 16816 KB Time limit exceeded
13 Correct 1787 ms 19540 KB Output is correct