oj.uz

Submission #97739

# Submission time Handle Problem Language Result Execution time Memory
97739 2019-02-17T21:58:54 Z jasony123123 Cake (CEOI14_cake) C++11
100 / 100
 1499 ms 22136 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 17 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 5400 KB Output is correct
2 Correct 274 ms 5280 KB Output is correct
3 Correct 370 ms 5528 KB Output is correct
4 Correct 229 ms 5496 KB Output is correct
5 Correct 742 ms 6724 KB Output is correct
6 Correct 497 ms 6892 KB Output is correct
7 Correct 383 ms 6664 KB Output is correct
8 Correct 228 ms 6776 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 7764 KB Output is correct
2 Correct 104 ms 7672 KB Output is correct
3 Correct 86 ms 7676 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 465 ms 17100 KB Output is correct
6 Correct 346 ms 17272 KB Output is correct
7 Correct 158 ms 17016 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1016 KB Output is correct
2 Correct 39 ms 1192 KB Output is correct
3 Correct 114 ms 4216 KB Output is correct
4 Correct 158 ms 4392 KB Output is correct
5 Correct 128 ms 1912 KB Output is correct
6 Correct 202 ms 6084 KB Output is correct
7 Correct 147 ms 2936 KB Output is correct
8 Correct 262 ms 8456 KB Output is correct
9 Correct 1499 ms 22076 KB Output is correct
10 Correct 485 ms 5368 KB Output is correct
11 Correct 721 ms 7096 KB Output is correct
12 Correct 1295 ms 18812 KB Output is correct
13 Correct 876 ms 22136 KB Output is correct