oj.uz

Submission #311146

# Submission time Handle Problem Language Result Execution time Memory
311146 2020-10-09T14:06:53 Z shivensinha4 Cake (CEOI14_cake) C++17
100 / 100
 1536 ms 11304 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 {
			//cout << "current set of elements is: ";
			//for (auto i: s) cout << i.first << " ";
			//cout << endl;
			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++;
			}
			
			//cout << "get new value " << nv << endl;
			tree.update(x, nv);
			ss.insert({nv, x});
			pt = 0;
			int ppt = -1;
			for (auto i: ss) {
				if (i.second == x) {
					ppt = pt;
					break;
				}
				pt++;
			}
			assert(ppt == y);
			swap(s, ss);
			//cout << "new set of elements is: ";
			//for (auto i: s) cout << i.first << " ";
			//cout << endl;
		}
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 22 ms 896 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 760 KB Output is correct
2 Correct 538 ms 888 KB Output is correct
3 Correct 587 ms 888 KB Output is correct
4 Correct 486 ms 892 KB Output is correct
5 Correct 744 ms 1280 KB Output is correct
6 Correct 688 ms 1400 KB Output is correct
7 Correct 612 ms 1400 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 363 ms 4464 KB Output is correct
2 Correct 256 ms 4464 KB Output is correct
3 Correct 270 ms 4336 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 381 ms 9892 KB Output is correct
6 Correct 439 ms 10020 KB Output is correct
7 Correct 386 ms 9636 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 512 KB Output is correct
2 Correct 83 ms 760 KB Output is correct
3 Correct 182 ms 2356 KB Output is correct
4 Correct 183 ms 2356 KB Output is correct
5 Correct 225 ms 760 KB Output is correct
6 Correct 361 ms 3060 KB Output is correct
7 Correct 313 ms 1400 KB Output is correct
8 Correct 287 ms 3832 KB Output is correct
9 Correct 1536 ms 11304 KB Output is correct
10 Correct 762 ms 1756 KB Output is correct
11 Correct 1026 ms 2680 KB Output is correct
12 Correct 1514 ms 9220 KB Output is correct
13 Correct 1519 ms 11068 KB Output is correct