Submission #1144720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144720		Muaath_5	Cake (CEOI14_cake)	C++20	0 / 100	539 ms	31828 KiB

cake

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e5+1;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
//using namespace __gnu_pbds; 
template<typename T>
using ordered_set = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;

#define int ll
#define pii pair<int, int>
int n, a, d[N];

#define seg pii

seg tree[4*N];
seg INF = {1e9, 1e9};

void update(int idx, seg val, int l=1, int r=n, int node=1) {
	if (l == r) {
		tree[node] = val;
		return;
	}
	const int mid = (l+r)/2;
	if (idx <= mid)
		update(idx, val, l, mid, node*2);
	else
		update(idx, val, mid+1, r, node*2+1);
	tree[node] = min(tree[node*2], tree[node*2+1]);
}

seg query(int ql, int qr, int l=1, int r=n, int node=1) {
	if (ql <= l && r <= qr) return tree[node];
	if (l > qr || r < ql) return INF;
	const int mid = (l+r)/2;
	return min(query(ql, qr, l, mid, node*2), query(ql, qr, mid+1, r, node*2+1));
}

seg cc[N];
map<int, int> cmp;
int g[N];

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> a;
	for (int i = 1; i <= n; cin >> d[i++]);
	ordered_set<pair<int, int>> oleft, oright;
	for (int i = 1; i < a; i++) {
		cc[i] = {n-d[i]+1, 0};
		oleft.insert(cc[i]);
		update(i, cc[i]);	
	}
	for (int i = a+1; i <= n; i++) {
		cc[i] = {n-d[i]+1, 0};
		oright.insert(cc[i]);
		update(i, cc[i]);
	}
	int q;
	cin >> q;
	int ttt = 1;
	while (q--) {
		ttt++;
		char t;
		int i, e;
		cin >> t >> i;
		if (t == 'F') {
			if (a == 1 || a == n) {
				cout << abs(a - i) << '\n';
				continue;
			}
			if (i == a) cout << "0\n";
			if (i < a) {
				auto suff_max = query(i, a-1);
				cout << (a-i) + oright.size()-oright.order_of_key(suff_max) << '\n';
			}
			if (i > a) {
				auto pref_max = query(a+1, i);
				cout << (i-a) + oleft.size()-oleft.order_of_key(pref_max) << '\n';
			}
		} else {
			cin >> e;
			if (i < a) oleft.erase(cc[i]);
			if (i > a) oright.erase(cc[i]);
			cc[i] = {e, -ttt};
			update(i, cc[i]);
			if (i < a) oleft.insert(cc[i]);
			if (i > a) oright.insert(cc[i]);
		}
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50