oj.uz

Submission #311141

# Submission time Handle Problem Language Result Execution time Memory
311141 2020-10-09T13:57:50 Z shivensinha4 Cake (CEOI14_cake) C++17
0 / 100
 1501 ms 10020 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});
			nums[x] = nv;
			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 0 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 Incorrect 699 ms 640 KB Output isn't correct
2 Incorrect 542 ms 720 KB Output isn't correct
3 Incorrect 589 ms 760 KB Output isn't correct
4 Correct 468 ms 760 KB Output is correct
5 Incorrect 748 ms 1152 KB Output isn't correct
6 Incorrect 685 ms 1272 KB Output isn't correct
7 Incorrect 634 ms 1192 KB Output isn't correct
8 Correct 478 ms 1272 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 381 ms 4208 KB Output isn't correct
2 Incorrect 254 ms 3952 KB Output isn't correct
3 Incorrect 279 ms 3956 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 374 ms 8880 KB Output isn't correct
6 Incorrect 423 ms 8868 KB Output isn't correct
7 Incorrect 351 ms 8612 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 684 KB Output isn't correct
2 Incorrect 81 ms 576 KB Output isn't correct
3 Incorrect 178 ms 2228 KB Output isn't correct
4 Incorrect 181 ms 2228 KB Output isn't correct
5 Incorrect 229 ms 888 KB Output isn't correct
6 Incorrect 363 ms 2804 KB Output isn't correct
7 Incorrect 324 ms 1144 KB Output isn't correct
8 Incorrect 289 ms 3572 KB Output isn't correct
9 Incorrect 1497 ms 9828 KB Output isn't correct
10 Incorrect 731 ms 1784 KB Output isn't correct
11 Incorrect 1044 ms 2424 KB Output isn't correct
12 Incorrect 1487 ms 8384 KB Output isn't correct
13 Incorrect 1501 ms 10020 KB Output isn't correct