oj.uz

Submission #413625

# Submission time Handle Problem Language Result Execution time Memory
413625 2021-05-29T06:36:07 Z sinamhdv Cake (CEOI14_cake) C++11
46.6667 / 100
 2000 ms 16324 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];
}

void add(int i, int x, int v = 1, int l = 0, int r = n - 1)
{
	seg[i] += x;
}

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;
}

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;
}

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;
}

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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 44 ms 972 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 5156 KB Output is correct
2 Correct 255 ms 5460 KB Output is correct
3 Correct 290 ms 5208 KB Output is correct
4 Correct 209 ms 5208 KB Output is correct
5 Correct 451 ms 6252 KB Output is correct
6 Correct 380 ms 6660 KB Output is correct
7 Correct 327 ms 6552 KB Output is correct
8 Correct 256 ms 6596 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 7244 KB Time limit exceeded
2 Execution timed out 2067 ms 7340 KB Time limit exceeded
3 Execution timed out 2077 ms 7452 KB Time limit exceeded
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 2074 ms 16056 KB Time limit exceeded
6 Execution timed out 2058 ms 16228 KB Time limit exceeded
7 Execution timed out 2079 ms 16324 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 908 KB Output is correct
2 Correct 103 ms 1108 KB Output is correct
3 Correct 1173 ms 4140 KB Output is correct
4 Correct 1200 ms 4216 KB Output is correct
5 Correct 204 ms 1748 KB Output is correct
6 Execution timed out 2067 ms 5580 KB Time limit exceeded
7 Correct 763 ms 2920 KB Output is correct
8 Correct 297 ms 8256 KB Output is correct
9 Execution timed out 2072 ms 16112 KB Time limit exceeded
10 Correct 672 ms 5304 KB Output is correct
11 Execution timed out 2070 ms 4964 KB Time limit exceeded
12 Execution timed out 2056 ms 13144 KB Time limit exceeded
13 Execution timed out 2078 ms 16124 KB Time limit exceeded