oj.uz

답안 #551754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551754 2022-04-21T12:29:15 Z AugustinasJucas 케이크 (CEOI14_cake) C++14
100 / 100
 1645 ms 20492 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));
		}
	}
	
	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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6100 KB Output is correct
2 Correct 5 ms 6100 KB Output is correct
3 Correct 6 ms 6212 KB Output is correct
4 Correct 12 ms 6304 KB Output is correct
5 Correct 27 ms 6728 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 746 ms 6744 KB Output is correct
2 Correct 419 ms 6788 KB Output is correct
3 Correct 526 ms 6792 KB Output is correct
4 Correct 280 ms 6792 KB Output is correct
5 Correct 815 ms 7468 KB Output is correct
6 Correct 678 ms 7508 KB Output is correct
7 Correct 540 ms 7488 KB Output is correct
8 Correct 338 ms 7508 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 11600 KB Output is correct
2 Correct 130 ms 11468 KB Output is correct
3 Correct 110 ms 11556 KB Output is correct
4 Correct 4 ms 6100 KB Output is correct
5 Correct 299 ms 18688 KB Output is correct
6 Correct 315 ms 18692 KB Output is correct
7 Correct 203 ms 18540 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 6556 KB Output is correct
2 Correct 58 ms 6612 KB Output is correct
3 Correct 157 ms 8840 KB Output is correct
4 Correct 167 ms 8828 KB Output is correct
5 Correct 233 ms 6868 KB Output is correct
6 Correct 296 ms 9864 KB Output is correct
7 Correct 223 ms 7244 KB Output is correct
8 Correct 377 ms 11036 KB Output is correct
9 Correct 1645 ms 20492 KB Output is correct
10 Correct 784 ms 7720 KB Output is correct
11 Correct 960 ms 8636 KB Output is correct
12 Correct 1528 ms 18248 KB Output is correct
13 Correct 1116 ms 19660 KB Output is correct