oj.uz

Submission #413632

# Submission time Handle Problem Language Result Execution time Memory
413632 2021-05-29T06:45:22 Z sinamhdv Cake (CEOI14_cake) C++11
100 / 100
 1470 ms 23020 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 250100
// Q limit = 500100 ///////////////////////////

int n, st, q;
int a[MAXN];
set<pii> s;
int seg[4 * MAXN];

void build(int v = 1, int l = 0, int r = n - 1)
{
	//FOR(i, 0, n) seg[i] = a[i];

	if (l == r)
	{
		seg[v] = a[l];
		return;
	}
	int mid = (r + l) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}

void add(int i, int x, int v = 1, int l = 0, int r = n - 1)
{
//	seg[i] += x;
	if (l == r)
	{
		seg[v] += x;
		return;
	}
	int mid = (r + l) / 2;
	if (i <= mid) add(i, x, 2 * v, l, mid);
	else add(i, x, 2 * v + 1, mid + 1, r);
	seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}

int getmax(int L, int R, int v = 1, int l = 0, int r = n - 1)
{
/*	int mx = 0;
	FOR(i, L, R + 1) mx = max(mx, seg[i]);
	return mx;*/

	if (l > R || r < L) return 0;
	if (l >= L && r <= R) return seg[v];
	int mid = (r + l) / 2;
	return max(getmax(L, R, 2 * v, l, mid), getmax(L, R, 2 * v + 1, mid + 1, r));
}

int findlpos(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
	/*int res = -1;
	FOR(i, L, R + 1) if (seg[i] > x) res = max(res, i);
	return res;*/

	if (l > R || r < L || seg[v] <= x) return -1;
	if (l == r) return l;
	int mid = (r + l) / 2;
	int pos = findlpos(L, R, x, 2 * v + 1, mid + 1, r);
	if (pos < 0) return findlpos(L, R, x, 2 * v, l, mid);
	return pos;
}

int findrpos(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
	/*int res = n;
	FOR(i, L, R + 1) if (seg[i] > x) return i;
	return res;*/

	if (l > R || r < L || seg[v] <= x) return n;
	if (l == r) return l;
	int mid = (r + l) / 2;
	int pos = findrpos(L, R, x, 2 * v, l, mid);
	if (pos >= n) return findrpos(L, R, x, 2 * v + 1, mid + 1, r);
	return pos;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> st;
	st--;
	FOR(i, 0, n) cin >> a[i], s.insert({a[i], i});

	build();

	cin >> q;
	while (q--)
	{
		char op;
		cin >> op;
		if (op == 'E')	// update
		{
			int i, x;
			cin >> i >> x;
			i--;
			vector<int> tmp;
			FOR(i, 0, x - 1)
			{
				tmp.pb(s.rbegin() -> sc);
				add(tmp.back(), 1);
				a[tmp.back()]++;
				s.erase(--s.end());
			}
			int cur;
			if (x > 1) cur = getmax(tmp.back(), tmp.back()) - 1;
			else cur = getmax(s.rbegin() -> sc, s.rbegin() -> sc) + 1;
			s.erase({a[i], i});
			add(i, cur - a[i]);
			a[i] = cur;
			s.insert({a[i], i});
			for (int u : tmp) s.insert({a[u], u});
		}
		else	// ask
		{
			int i;
			cin >> i;
			i--;
			if (i < st)
			{
				int mx = getmax(i, st - 1);
				int pos = findrpos(st + 1, n - 1, mx);	// upper_bound
				cout << pos - i - 1 << endl;
			}
			else if (i > st)
			{
				int mx = getmax(st + 1, i);
				int pos = findlpos(0, st - 1, mx);	// handle st == 0 //////////////////////////////////////
				cout << i - pos - 1 << endl;
			}
			else
			{
				cout << "0\n";
			}
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 7 ms 440 KB Output is correct
5 Correct 18 ms 1096 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 5232 KB Output is correct
2 Correct 397 ms 5284 KB Output is correct
3 Correct 460 ms 5276 KB Output is correct
4 Correct 360 ms 5316 KB Output is correct
5 Correct 809 ms 6408 KB Output is correct
6 Correct 667 ms 6852 KB Output is correct
7 Correct 534 ms 6688 KB Output is correct
8 Correct 407 ms 6816 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 8336 KB Output is correct
2 Correct 104 ms 8124 KB Output is correct
3 Correct 86 ms 8328 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 271 ms 18120 KB Output is correct
6 Correct 256 ms 18156 KB Output is correct
7 Correct 139 ms 17940 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1000 KB Output is correct
2 Correct 48 ms 1092 KB Output is correct
3 Correct 119 ms 4584 KB Output is correct
4 Correct 146 ms 4448 KB Output is correct
5 Correct 185 ms 1836 KB Output is correct
6 Correct 290 ms 6236 KB Output is correct
7 Correct 194 ms 3028 KB Output is correct
8 Correct 333 ms 8900 KB Output is correct
9 Correct 1405 ms 22952 KB Output is correct
10 Correct 624 ms 5180 KB Output is correct
11 Correct 847 ms 7188 KB Output is correct
12 Correct 1470 ms 19968 KB Output is correct
13 Correct 1000 ms 23020 KB Output is correct