Submission #97739

#	Time	Username	Problem	Language	Result	Execution time	Memory
97739		jasony123123	Cake (CEOI14_cake)	C++11	100 / 100	1499 ms	22136 KiB

cake

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll INF = 1e14;
/***********************CEOI 2014 D2 Cake*****************************************/
template<int SZ, class T> struct SegmentTree {
	T data[2 * SZ];
	int _N;

	T id = 0; // identity function (a,id) = a; (id,a) = a;
	T combine(T a, T b) {
		return max(a, b);
	}

	SegmentTree() {}
	void build(int N) {
		_N = N;
		for (int i = _N - 1; i > 0; --i)
			data[i] = combine(data[i << 1], data[(i << 1) | 1]);
	}

	void update(int p, T val) {
		data[p + _N] = val;
		for (p += _N; p > 1; p >>= 1)
			data[p >> 1] = combine(data[p], data[p ^ 1]);
	}
	T query(int l, int r) { // sum [l,r]
		r++;
		T resl = id, resr = id;
		for (l += _N, r += _N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) resl = combine(resl, data[l++]);
			if (r & 1) resr = combine(data[--r], resr);
		}
		return combine(resl, resr);
	}
};

int n, md;

set<pii, greater<pii>> nums;
SegmentTree<250009, int> tree;

void enhance() {
	int p, e; cin >> p >> e;
	v<pii> firste;
	FOR(x, 0, e) {
		firste.push_back(*nums.begin());
		if (x != e - 1)
			nums.erase(nums.begin());
	}
	FOR(x, 0, e - 1) {
		tree.update(firste[x].second, firste[x].first + 1);
		nums.insert({ firste[x].first + 1, firste[x].second });
	}
	int old = tree.query(p, p);
	tree.update(p, firste[e - 1].first + 1);
	nums.erase({ old,p });
	nums.insert({ firste[e - 1].first + 1 , p });

/*	cout << "enhancement (pos order): \n";
	for (auto x : nums)
		cout << x.second << "\n";*/
}

void request() {
	int x; cin >> x;
	if (x == md) {
		cout << "0\n";
	}
	else if (x < md) {
		int mx = tree.query(x, md - 1);
		int lo = md + 1, hi = n + 1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (tree.query(md + 1, mid) < mx)
				lo = mid + 1;
			else
				hi = mid;
		}
		cout << lo - x - 1 << "\n";
	}
	else {
		int mx = tree.query(md + 1, x);
		int lo = 1, hi = md;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (tree.query(md - mid, md - 1) < mx)
				lo = mid + 1;
			else
				hi = mid;
		}
		cout << x - (md - lo) - 1 << "\n";
	}
}

int main() {
	io();
	cin >> n >> md;
	FORE(i, 1, n) {
		int x; cin >> x;
		tree.data[n + 2 + i] = x;
		nums.insert({ x, i });
	}
	tree.data[n + 2 + 0] = tree.data[n + 2 + n + 1] = 1 << 30;
	tree.build(n + 2);
	
	int q; cin >> q;
	while (q--) {
		char c; cin >> c;
		if (c == 'E')
			enhance();
		else
			request();
	}
}

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