oj.uz

Submission #84029

# Submission time Handle Problem Language Result Execution time Memory
84029 2018-11-12T12:45:06 Z aminra Cake (CEOI14_cake) C++17
0 / 100
 1228 ms 57696 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int infint = 1e9;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)250003;
int n, s, q, a[MAXN], seg[4 * MAXN], pos[MAXN];
void build(int node, int st, int en)
{
	if(en - st < 2)
	{
		seg[node] = a[st];
		return;
	}
	int mid = (st + en) >> 1;
	build(node << 1, st, mid);
	build(node << 1 | 1, mid, en);
	seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
void update(int node, int st, int en, int idx, int val)
{
	if(en - st < 2)
	{
		seg[node] = val;
		return;
	}
	int mid = (st + en) >> 1;
	if(idx < mid)
		update(node << 1, st, mid, idx, val);
	else
		update(node << 1 | 1, mid, en, idx, val);
	seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
int get(int node, int st, int en, int l, int r)
{
	if(l >= en || st >= r)
		return 0;
	if(l <= st && en <= r)
		return seg[node];
	int mid = (st + en) >> 1;
	return max(get(node << 1, st, mid, l, r), get(node << 1 | 1, mid, en, l, r));
}
set< pair<int, int> > gre;
int main()
{
	//you think I'm wat? coding machine?
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> s;
	s--;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		pos[a[i]] = i;
	}
	build(1, 0, n);
	for (int i = n; i >= max(0, n - 9); i--)
		gre.insert({i, pos[i]});
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		char type;
		cin >> type;
		if(type == 'E')
		{
			int idx, val;
			cin >> idx >> val;
			idx--, val--;
			auto it = gre.rbegin();
			for (int j = 0; j < val; j++)
				it--;
			int cur = (*it).first + 1;
			update(1, 0, n, idx, cur);
			int tmp = cur;
			it++;
			vector< pair<int, int> > changes, del;
			for (int j = 0; j < val; j++)
			{
				if((*it).first == cur)
					changes.push_back({(*it).second, ++cur}), del.push_back({(*it).second, cur - 1});
				it++;
			}
			for (auto u : del)
				gre.erase(u);
			for (auto u : changes)
			{
				update(1, 0, n, u.first, u.second);
				gre.insert(u);
			}
			gre.insert({idx, tmp});
			if(gre.size() > 10)
			{
				pair<int, int> beg = *gre.begin();
				gre.erase(beg);
			}
		}
		else
		{
			int idx;
			cin >> idx;
			idx--;
			if(idx == s)
			{
				cout << 0 << "\n";
				continue;
			}
			if(idx < s)
			{
				int mx = get(1, 0, n, idx, s + 1);
				int L = s - 1, R = n;
				while(R - L > 1)
				{
					int mid = (L + R) >> 1;
					if(get(1, 0, n, s, mid + 1) > mx)
						R = mid;
					else
						L = mid;
				}
				cout << R - idx - 1 << "\n";
			}
			else
			{
				int mx = get(1, 0, n, s, idx + 1);
				int L = -1, R = s;
				while(R - L > 1)
				{
					int mid = (L + R) >> 1;
					if(get(1, 0, n, mid, s + 1) > mx)
						L = mid;
					else
						R = mid;
				}
				cout << idx - L - 1 << "\n";
			}
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 4084 KB Output isn't correct
2 Incorrect 185 ms 7496 KB Output isn't correct
3 Incorrect 218 ms 10896 KB Output isn't correct
4 Incorrect 184 ms 14324 KB Output isn't correct
5 Incorrect 231 ms 18676 KB Output isn't correct
6 Incorrect 249 ms 23132 KB Output isn't correct
7 Incorrect 222 ms 27360 KB Output isn't correct
8 Incorrect 216 ms 31708 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 33628 KB Output isn't correct
2 Incorrect 280 ms 33640 KB Output isn't correct
3 Incorrect 242 ms 33640 KB Output isn't correct
4 Incorrect 2 ms 33640 KB Output isn't correct
5 Incorrect 462 ms 35912 KB Output isn't correct
6 Incorrect 444 ms 36048 KB Output isn't correct
7 Incorrect 404 ms 36048 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 36048 KB Output isn't correct
2 Incorrect 70 ms 36048 KB Output isn't correct
3 Incorrect 186 ms 36048 KB Output isn't correct
4 Incorrect 124 ms 36048 KB Output isn't correct
5 Incorrect 133 ms 36048 KB Output isn't correct
6 Incorrect 309 ms 36048 KB Output isn't correct
7 Incorrect 231 ms 36048 KB Output isn't correct
8 Incorrect 125 ms 36048 KB Output isn't correct
9 Incorrect 1057 ms 44412 KB Output isn't correct
10 Incorrect 426 ms 44412 KB Output isn't correct
11 Incorrect 705 ms 44768 KB Output isn't correct
12 Incorrect 1079 ms 52800 KB Output isn't correct
13 Incorrect 1228 ms 57696 KB Output isn't correct