oj.uz

답안 #311147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311147 2020-10-09T14:07:36 Z shivensinha4 케이크 (CEOI14_cake) C++17
100 / 100
 1552 ms 11172 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

class SegmentTree {
	private:
		vi tree, raw; int n;
		
		int merge(int a, int b) {
			return max(a, b);
		}
		
		void buildTree(int l, int r, int p) {
			if (l == r) {
				tree[p] = raw[l];
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			buildTree(l, mid, c1); buildTree(mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		void update(int i, int val, int l, int r, int p) {
			if (l > i or r < i) return;
			if (l == r) {
				tree[p] = val;
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		int mx(int i, int j, int l, int r, int p) {
			if (l > j or r < i) return 0;
			if (l >= i and r <= j) return tree[p];
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			return merge(mx(i, j, l, mid, c1), mx(i, j, mid+1, r, c2));
		}
	
	public: 
		SegmentTree(vi input) {
			raw = input;
			n = raw.size();
			tree.resize(4*n);
			buildTree(0, n-1, 0);
		}
		
		int mx(int i, int j) {
			return mx(i, j, 0, n-1, 0);
		}
		
		void update(int i, int val) {
			update(i, val, 0, n-1, 0);
		}
};

const int MXV = 750000;
int pos[MXV+2];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, a, q; cin >> n >> a;
	a -= 1;
	vi nums(n);
	for_(i, 0, n) {
		cin >> nums[i];
		pos[nums[i]] = i;
	}
	SegmentTree tree(nums);
	vector<ii> mod(n);
	for_(i, 0, n) mod[i] = {nums[i], i};
	sort(mod.begin(), mod.end(), greater<ii>());
	set<ii, greater<ii>> s;
	for_(i, 0, min(10, n)) s.insert({mod[i].first, mod[i].second});
	
	cin >> q;
	while (q--) {
		char c; cin >> c;
		if (c == 'F') {
			int k; cin >> k;
			k -= 1;
			
			if (k == a) {
				cout << 0 << endl;
				continue;
			}
			int bef = abs(k-a), lo, hi, ans, largest;
			if (k < a) {
				largest = tree.mx(k, a-1);
				lo = a+1, hi = ans = n;
				while (lo < hi) {
					int mid = (lo+hi)/2;
					if (tree.mx(a+1, mid) >= largest) {
						ans = hi = mid;
					} else {
						lo = mid+1;
					}
				}
			} else {
				largest = tree.mx(a+1, k);
				lo = 0, hi = a, ans = -1;
				while (lo < hi) {
					int mid = (lo+hi)/2;
					if (tree.mx(mid, a-1) >= largest) {
						ans = mid;
						lo = mid+1;
					} else {
						hi = mid;
					}
				}
			}
			
			cout << bef+abs(ans-a)-1 << endl;
		} else {
			int x, y; cin >> x >> y;
			set<ii, greater<ii>> ss;
			x -= 1; y -= 1;
			int pt = 0, nv = -1;
			for (auto i: s) {
				if (ss.size()+1 == s.size()) break;
				else if (pt >= y) {
					if (i.second != x) {
						if (nv == -1) nv = i.first+1;
						ss.insert(i);
					}
				}
				else {
					tree.update(i.second, i.first+1);
					nums[i.second] += 1;
					ss.insert({i.first+1, i.second});	
					nv = i.first;
				}
				pt++;
			}
			
			tree.update(x, nv);
			ss.insert({nv, x});
			swap(s, ss);
		}
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 22 ms 768 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 714 ms 756 KB Output is correct
2 Correct 547 ms 768 KB Output is correct
3 Correct 580 ms 888 KB Output is correct
4 Correct 487 ms 768 KB Output is correct
5 Correct 747 ms 1372 KB Output is correct
6 Correct 673 ms 1280 KB Output is correct
7 Correct 603 ms 1400 KB Output is correct
8 Correct 496 ms 1280 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 4604 KB Output is correct
2 Correct 250 ms 4464 KB Output is correct
3 Correct 261 ms 4336 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 380 ms 9868 KB Output is correct
6 Correct 447 ms 9892 KB Output is correct
7 Correct 372 ms 9636 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 512 KB Output is correct
2 Correct 86 ms 640 KB Output is correct
3 Correct 185 ms 2356 KB Output is correct
4 Correct 188 ms 2484 KB Output is correct
5 Correct 226 ms 888 KB Output is correct
6 Correct 362 ms 3060 KB Output is correct
7 Correct 308 ms 1272 KB Output is correct
8 Correct 287 ms 3952 KB Output is correct
9 Correct 1552 ms 10828 KB Output is correct
10 Correct 749 ms 1656 KB Output is correct
11 Correct 1029 ms 2664 KB Output is correct
12 Correct 1529 ms 9216 KB Output is correct
13 Correct 1532 ms 11172 KB Output is correct