oj.uz

Submission #311143

# Submission time Handle Problem Language Result Execution time Memory
311143 2020-10-09T14:02:44 Z shivensinha4 Cake (CEOI14_cake) C++17
0 / 100
 1518 ms 13800 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);
	vi mod = nums;
	sort(mod.begin(), mod.end(), greater<int>());
	set<ii, greater<ii>> s;
	for_(i, 0, min(10, n)) s.insert({mod[i], i});
	
	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 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 1020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 551 ms 640 KB Output isn't correct
3 Runtime error 17 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 483 ms 640 KB Output is correct
5 Runtime error 82 ms 2044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 331 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 28 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 491 ms 1152 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 4244 KB Output isn't correct
2 Incorrect 247 ms 3952 KB Output isn't correct
3 Incorrect 267 ms 3996 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 383 ms 8868 KB Output isn't correct
6 Incorrect 426 ms 8868 KB Output isn't correct
7 Incorrect 366 ms 8616 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 512 KB Output isn't correct
2 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 179 ms 2084 KB Output isn't correct
4 Incorrect 184 ms 2100 KB Output isn't correct
5 Incorrect 220 ms 760 KB Output isn't correct
6 Runtime error 348 ms 5108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 7 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 285 ms 3456 KB Output isn't correct
9 Incorrect 1510 ms 9820 KB Output isn't correct
10 Incorrect 735 ms 1528 KB Output isn't correct
11 Runtime error 12 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 604 ms 13800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Incorrect 1518 ms 9892 KB Output isn't correct