oj.uz

Submission #84028

# Submission time Handle Problem Language Result Execution time Memory
84028 2018-11-12T12:35:10 Z aminra Cake (CEOI14_cake) C++14
0 / 100
 44 ms 4604 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()
{
	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]});
	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 << "\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 << "\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 3 ms 640 KB Output isn't correct
2 Incorrect 3 ms 808 KB Output isn't correct
3 Incorrect 4 ms 808 KB Output isn't correct
4 Incorrect 3 ms 808 KB Output isn't correct
5 Incorrect 5 ms 896 KB Output isn't correct
6 Incorrect 5 ms 1004 KB Output isn't correct
7 Incorrect 5 ms 1044 KB Output isn't correct
8 Incorrect 5 ms 1044 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2356 KB Output isn't correct
2 Incorrect 13 ms 2356 KB Output isn't correct
3 Incorrect 13 ms 2512 KB Output isn't correct
4 Incorrect 2 ms 2512 KB Output isn't correct
5 Incorrect 40 ms 4536 KB Output isn't correct
6 Incorrect 39 ms 4576 KB Output isn't correct
7 Incorrect 31 ms 4576 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4576 KB Output isn't correct
2 Incorrect 3 ms 4576 KB Output isn't correct
3 Incorrect 13 ms 4576 KB Output isn't correct
4 Incorrect 8 ms 4576 KB Output isn't correct
5 Incorrect 2 ms 4576 KB Output isn't correct
6 Incorrect 10 ms 4576 KB Output isn't correct
7 Incorrect 4 ms 4576 KB Output isn't correct
8 Incorrect 15 ms 4576 KB Output isn't correct
9 Incorrect 42 ms 4604 KB Output isn't correct
10 Incorrect 2 ms 4604 KB Output isn't correct
11 Incorrect 6 ms 4604 KB Output isn't correct
12 Incorrect 30 ms 4604 KB Output isn't correct
13 Incorrect 44 ms 4604 KB Output isn't correct