oj.uz

Submission #311144

# Submission time Handle Problem Language Result Execution time Memory
311144 2020-10-09T14:04:45 Z shivensinha4 Cake (CEOI14_cake) C++17
0 / 100
 1652 ms 10916 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 = tree.mx(min(a, k), max(a, k));
			if (k < a) {
				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 {
				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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 752 KB Output is correct
2 Incorrect 555 ms 888 KB Output isn't correct
3 Correct 632 ms 800 KB Output is correct
4 Correct 519 ms 792 KB Output is correct
5 Correct 792 ms 1376 KB Output is correct
6 Incorrect 698 ms 1280 KB Output isn't correct
7 Correct 649 ms 1380 KB Output is correct
8 Correct 511 ms 1388 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4496 KB Output is correct
2 Incorrect 281 ms 4508 KB Output isn't correct
3 Incorrect 305 ms 4592 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 369 ms 9872 KB Output is correct
6 Correct 443 ms 9856 KB Output is correct
7 Incorrect 416 ms 9892 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 512 KB Output isn't correct
2 Incorrect 86 ms 632 KB Output isn't correct
3 Incorrect 197 ms 2388 KB Output isn't correct
4 Incorrect 195 ms 2348 KB Output isn't correct
5 Incorrect 239 ms 788 KB Output isn't correct
6 Incorrect 382 ms 3060 KB Output isn't correct
7 Incorrect 317 ms 1272 KB Output isn't correct
8 Correct 300 ms 3952 KB Output is correct
9 Incorrect 1652 ms 10916 KB Output isn't correct
10 Incorrect 772 ms 1532 KB Output isn't correct
11 Incorrect 1030 ms 2456 KB Output isn't correct
12 Correct 1581 ms 9060 KB Output is correct
13 Correct 1508 ms 10856 KB Output is correct