oj.uz

Submission #311137

# Submission time Handle Problem Language Result Execution time Memory
311137 2020-10-09T13:54:41 Z shivensinha4 Cake (CEOI14_cake) C++17
0 / 100
 1387 ms 16216 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;
		//cout << "..." << c << " " << k << endl;
		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 (pt == s.size()-1) 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;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:139:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int>, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     if (pt == s.size()-1) break;
      |         ~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 344 ms 5040 KB Output isn't correct
2 Incorrect 306 ms 5368 KB Output isn't correct
3 Incorrect 336 ms 5368 KB Output isn't correct
4 Correct 198 ms 5240 KB Output is correct
5 Incorrect 373 ms 6008 KB Output isn't correct
6 Incorrect 362 ms 6264 KB Output isn't correct
7 Incorrect 348 ms 6136 KB Output isn't correct
8 Correct 207 ms 6136 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 5616 KB Output isn't correct
2 Incorrect 253 ms 5440 KB Output isn't correct
3 Incorrect 258 ms 5232 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 368 ms 11428 KB Output isn't correct
6 Incorrect 427 ms 11300 KB Output isn't correct
7 Incorrect 351 ms 11172 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 896 KB Output isn't correct
2 Incorrect 77 ms 1144 KB Output isn't correct
3 Incorrect 183 ms 3124 KB Output isn't correct
4 Incorrect 166 ms 3124 KB Output isn't correct
5 Incorrect 136 ms 1912 KB Output isn't correct
6 Incorrect 352 ms 4468 KB Output isn't correct
7 Incorrect 271 ms 2808 KB Output isn't correct
8 Incorrect 185 ms 6000 KB Output isn't correct
9 Incorrect 1373 ms 16164 KB Output isn't correct
10 Incorrect 460 ms 5240 KB Output isn't correct
11 Incorrect 786 ms 6872 KB Output isn't correct
12 Incorrect 1387 ms 14184 KB Output isn't correct
13 Incorrect 1272 ms 16216 KB Output isn't correct