oj.uz

Submission #311152

# Submission time Handle Problem Language Result Execution time Memory
311152 2020-10-09T14:15:28 Z shivensinha4 Cake (CEOI14_cake) C++17
100 / 100
 1586 ms 10020 KB 
/*
 * Similar to editorial, but I just use one segment tree that supports updates and range max.
 * To find "longest sequence such that all elements are less that d starting at a" on either side of a, I use binary search.
 * This does make it log^2(n), but passes easily.
 */
 
#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);
		}
};

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];
	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 21 ms 768 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 764 KB Output is correct
2 Correct 543 ms 640 KB Output is correct
3 Correct 577 ms 760 KB Output is correct
4 Correct 479 ms 640 KB Output is correct
5 Correct 749 ms 1272 KB Output is correct
6 Correct 665 ms 1400 KB Output is correct
7 Correct 603 ms 1272 KB Output is correct
8 Correct 499 ms 1400 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4080 KB Output is correct
2 Correct 255 ms 3952 KB Output is correct
3 Correct 266 ms 3912 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 379 ms 8868 KB Output is correct
6 Correct 439 ms 8868 KB Output is correct
7 Correct 381 ms 8740 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 512 KB Output is correct
2 Correct 83 ms 632 KB Output is correct
3 Correct 184 ms 2100 KB Output is correct
4 Correct 202 ms 2168 KB Output is correct
5 Correct 229 ms 716 KB Output is correct
6 Correct 376 ms 2928 KB Output is correct
7 Correct 309 ms 1148 KB Output is correct
8 Correct 288 ms 3568 KB Output is correct
9 Correct 1586 ms 9904 KB Output is correct
10 Correct 761 ms 1528 KB Output is correct
11 Correct 1058 ms 2492 KB Output is correct
12 Correct 1573 ms 8396 KB Output is correct
13 Correct 1550 ms 10020 KB Output is correct