oj.uz

Submission #84034

# Submission time Handle Problem Language Result Execution time Memory
84034 2018-11-12T13:02:11 Z aminra Cake (CEOI14_cake) C++14
0 / 100
 1641 ms 10540 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);
			}
			/*for (int j = 0; j < n; j++)
				cout << get(1, 0, n, j, j + 1) << " ";
			cout << endl;*/
		}
		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 320 ms 892 KB Output isn't correct
2 Incorrect 311 ms 892 KB Output isn't correct
3 Incorrect 329 ms 1144 KB Output isn't correct
4 Incorrect 189 ms 1144 KB Output isn't correct
5 Incorrect 406 ms 2400 KB Output isn't correct
6 Incorrect 350 ms 2400 KB Output isn't correct
7 Incorrect 345 ms 2400 KB Output isn't correct
8 Incorrect 205 ms 2400 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 2972 KB Output isn't correct
2 Incorrect 329 ms 3040 KB Output isn't correct
3 Incorrect 292 ms 3056 KB Output isn't correct
4 Incorrect 2 ms 3056 KB Output isn't correct
5 Incorrect 460 ms 5376 KB Output isn't correct
6 Incorrect 529 ms 5376 KB Output isn't correct
7 Incorrect 514 ms 5412 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 5412 KB Output isn't correct
2 Incorrect 87 ms 5412 KB Output isn't correct
3 Incorrect 186 ms 5412 KB Output isn't correct
4 Incorrect 154 ms 5412 KB Output isn't correct
5 Incorrect 208 ms 5412 KB Output isn't correct
6 Incorrect 372 ms 5412 KB Output isn't correct
7 Incorrect 311 ms 5412 KB Output isn't correct
8 Incorrect 155 ms 5412 KB Output isn't correct
9 Incorrect 1476 ms 10292 KB Output isn't correct
10 Incorrect 590 ms 10292 KB Output isn't correct
11 Incorrect 940 ms 10292 KB Output isn't correct
12 Incorrect 1456 ms 10540 KB Output isn't correct
13 Incorrect 1641 ms 10540 KB Output isn't correct