oj.uz

답안 #551730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551730 2022-04-21T11:46:39 Z AugustinasJucas 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 28012 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8148 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8176 KB Output is correct
4 Correct 19 ms 8264 KB Output is correct
5 Correct 39 ms 8772 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 840 ms 12912 KB Output is correct
2 Correct 468 ms 12956 KB Output is correct
3 Correct 551 ms 12960 KB Output is correct
4 Correct 319 ms 13136 KB Output is correct
5 Correct 877 ms 13900 KB Output is correct
6 Correct 724 ms 14304 KB Output is correct
7 Correct 598 ms 14308 KB Output is correct
8 Correct 319 ms 14344 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 14744 KB Output is correct
2 Correct 348 ms 14568 KB Output is correct
3 Correct 351 ms 14540 KB Output is correct
4 Correct 7 ms 8148 KB Output is correct
5 Correct 605 ms 23232 KB Output is correct
6 Correct 469 ms 22936 KB Output is correct
7 Correct 433 ms 22828 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 8812 KB Output is correct
2 Correct 111 ms 8992 KB Output is correct
3 Correct 246 ms 11732 KB Output is correct
4 Correct 280 ms 11720 KB Output is correct
5 Correct 352 ms 9676 KB Output is correct
6 Correct 426 ms 13320 KB Output is correct
7 Correct 427 ms 10944 KB Output is correct
8 Correct 330 ms 15336 KB Output is correct
9 Execution timed out 2094 ms 27280 KB Time limit exceeded
10 Correct 1152 ms 13092 KB Output is correct
11 Correct 1468 ms 14708 KB Output is correct
12 Execution timed out 2080 ms 24884 KB Time limit exceeded
13 Correct 1838 ms 28012 KB Output is correct