oj.uz

Submission #391941

# Submission time Handle Problem Language Result Execution time Memory
391941 2021-04-20T08:23:21 Z 8e7 Cake (CEOI14_cake) C++14
100 / 100
 902 ms 9108 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 250005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_upate>;

int arr[maxn], a[2][maxn], orig[2][maxn];
pii big[11];
vector<pii> vec;

int al, bl;
struct segtree{
	int seg[4 * maxn];
	void init(int cur, int l, int r, int v[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = v[l];
			return;
		}
		int mid = (l + r) / 2;
		init(cur * 2, l, mid, v);
		init(cur * 2 + 1, mid, r, v);
		seg[cur] = max(seg[cur * 2], seg[cur * 2 + 1]);
	}
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = val;
			return;
		}
		int mid = (l + r) / 2;
		if (ind < mid) modify(cur * 2, l, mid, ind, val);
		else modify(cur * 2 + 1, mid, r, ind, val);
		seg[cur] = max(seg[cur * 2], seg[cur * 2 + 1]);
		//cout << l << " " << r << " " << seg[cur] << endl;
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return 0;
		//cout << l << " " << r << " " << ql << " " << qr << endl;
		if (ql <= l && qr >= r) return seg[cur];
		int mid = (l + r) / 2;
		return max(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));
	}
	int search(int cur, int l, int r, int val, int num) {
		//cout << l << " " << r << " " << val << " " << seg[cur] << endl;
		if (r <= l) return l;
		if (r - l == 1) {
			return max(num, seg[cur]) < val ? r : l;
		}

		int mid = (l + r) / 2;
		if (max(num, seg[cur * 2]) < val) return search(cur * 2 + 1, mid, r, val, max(num, seg[cur * 2]));
		else return search(cur * 2, l, mid, val, num);
	}
} sl, sr;


int main() {
	io
	int n, st;
	cin >> n >> st;
	st--;
	al = st, bl = n - 1 - st;
	for (int i = 0;i < n;i++) {
		cin >> arr[i];
		vec.push_back(make_pair(arr[i], i));
		if (i < st) orig[0][st - i - 1] = arr[i]; //1 base
		else if (i > st) orig[1][i - st - 1] = arr[i];
	}
	sort(vec.begin(), vec.end());
	for (int i = max(0, n - 10);i < n;i++) {
		big[n - i - 1] = vec[i]; //0~9
	}
	sl.init(1, 0, al, orig[0]);
	sr.init(1, 0, bl, orig[1]);

	int q;
	cin >> q;
	while (q--) {
		char type;
		cin >> type;
		if (type == 'E') {
			int ind, pos;
			cin >> ind>> pos;
			ind--, pos--;
			int orig = min(9, n - 1);
			for (int i = 0;i < min(10, n);i++) {
				if (big[i].ss == ind) {
					orig = i;
					break;
				}
			}

			int val = big[pos].ff + 1;
			for (int i = 0;i < pos;i++) {
				int id = big[i].ss;
				big[i].ff++;
				if (id < st) {
					//cout << "l " << st - id - 1 << " " << big[i].ff << endl;
					sl.modify(1, 0, al, st - id - 1, big[i].ff);
				} else if (id > st) {
					//cout << "r " << id - st - 1 << " " << big[i].ff << endl;
					sr.modify(1, 0, bl, id - st - 1, big[i].ff);
				}
			}
			for (int i = orig;i > pos;i--) big[i] = big[i - 1];
			big[pos].ss = ind;
			big[pos].ff++;
			if (ind < st) {
				//cout << "l " << st - ind - 1 << " " << val << endl;
				sl.modify(1, 0, al, st - ind - 1, val);
			} else if (ind > st) {
				//cout << "r " << ind - st - 1 << " " << val << endl;
				sr.modify(1, 0, bl, ind - st - 1, val);
			}
			/*
			for (int i = 0;i < n;i++) {
				cout << big[i].ff << " " << big[i].ss << endl;
			}
			*/

		} else {
			int ind;
			cin >> ind;
			ind--;
			if (ind == st) {
				cout << 0 << "\n";
			} else if (ind < st) {
				int p = st - ind - 1;
				int pref = sl.query(1, 0, al, 0, p + 1);
				cout << sr.search(1, 0, bl, pref, 0) + p + 1 << "\n";
			} else {
				int p = ind - st - 1;
				int pref = sr.query(1, 0, bl, 0, p + 1);
				cout << sl.search(1, 0, al, pref, 0) + p + 1 << "\n";
			}
		}
	}
}
/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
 */

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 7 ms 396 KB Output is correct
5 Correct 17 ms 716 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 716 KB Output is correct
2 Correct 129 ms 752 KB Output is correct
3 Correct 189 ms 756 KB Output is correct
4 Correct 128 ms 716 KB Output is correct
5 Correct 286 ms 1104 KB Output is correct
6 Correct 220 ms 1104 KB Output is correct
7 Correct 216 ms 1104 KB Output is correct
8 Correct 142 ms 1104 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 3648 KB Output is correct
2 Correct 220 ms 3520 KB Output is correct
3 Correct 218 ms 3544 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 259 ms 7040 KB Output is correct
6 Correct 258 ms 7012 KB Output is correct
7 Correct 241 ms 6840 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 504 KB Output is correct
2 Correct 62 ms 608 KB Output is correct
3 Correct 111 ms 1944 KB Output is correct
4 Correct 127 ms 1936 KB Output is correct
5 Correct 200 ms 744 KB Output is correct
6 Correct 214 ms 2748 KB Output is correct
7 Correct 251 ms 1148 KB Output is correct
8 Correct 125 ms 3092 KB Output is correct
9 Correct 902 ms 8196 KB Output is correct
10 Correct 671 ms 1444 KB Output is correct
11 Correct 748 ms 2656 KB Output is correct
12 Correct 898 ms 7340 KB Output is correct
13 Correct 822 ms 9108 KB Output is correct