oj.uz

Submission #311139

# Submission time Handle Problem Language Result Execution time Memory
311139 2020-10-09T13:56:28 Z shivensinha4 Cake (CEOI14_cake) C++17
0 / 100
 1385 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 (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++;
			}
			
			if (nv == -1) assert(false);
			//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:138: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]
  138 |     if (pt == s.size()-1) break;
      |         ~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 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 329 ms 640 KB Output isn't correct
2 Incorrect 296 ms 640 KB Output isn't correct
3 Incorrect 309 ms 640 KB Output isn't correct
4 Correct 199 ms 640 KB Output is correct
5 Incorrect 351 ms 1272 KB Output isn't correct
6 Incorrect 350 ms 1152 KB Output isn't correct
7 Incorrect 336 ms 1272 KB Output isn't correct
8 Correct 210 ms 1152 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 4184 KB Output isn't correct
2 Incorrect 254 ms 3952 KB Output isn't correct
3 Incorrect 271 ms 3956 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 383 ms 8872 KB Output isn't correct
6 Incorrect 437 ms 8996 KB Output isn't correct
7 Incorrect 366 ms 8612 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 668 KB Output isn't correct
2 Incorrect 74 ms 632 KB Output isn't correct
3 Incorrect 179 ms 2100 KB Output isn't correct
4 Incorrect 168 ms 2232 KB Output isn't correct
5 Incorrect 136 ms 760 KB Output isn't correct
6 Incorrect 354 ms 2804 KB Output isn't correct
7 Incorrect 272 ms 1144 KB Output isn't correct
8 Incorrect 177 ms 3456 KB Output isn't correct
9 Incorrect 1385 ms 9928 KB Output isn't correct
10 Incorrect 449 ms 1528 KB Output isn't correct
11 Incorrect 783 ms 2508 KB Output isn't correct
12 Incorrect 1373 ms 8296 KB Output isn't correct
13 Incorrect 1256 ms 10020 KB Output isn't correct