oj.uz

Submission #84043

# Submission time Handle Problem Language Result Execution time Memory
84043 2018-11-12T13:27:10 Z aminra Cake (CEOI14_cake) C++14
0 / 100
 1330 ms 6588 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(1, 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();
			vector<pair<int, int> > lrg;
			for (auto u : gre)
				lrg.push_back(u);
			int cur = lrg[lrg.size() - val - 1].first + 1;
			update(1, 0, n, idx, cur);
			int tmp = cur;
			it--;
			vector< pair<int, int> > changes, del;
			for (int j = lrg.size() - val; j < lrg.size(); j++)
			{
				if(lrg[j].first == cur)
					changes.push_back({++cur, lrg[j].second}), del.push_back({cur - 1, lrg[j].second});
				it--;
			}
			for (auto u : del)
				gre.erase(u);
			for (auto u : changes)
			{
				update(1, 0, n, u.second, u.first);
				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";
			}
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:79:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = lrg.size() - val; j < lrg.size(); j++)
                                   ~~^~~~~~~~~~~~

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 339 ms 748 KB Output isn't correct
2 Incorrect 416 ms 748 KB Output isn't correct
3 Incorrect 475 ms 748 KB Output isn't correct
4 Incorrect 445 ms 876 KB Output isn't correct
5 Incorrect 365 ms 1076 KB Output isn't correct
6 Incorrect 372 ms 1076 KB Output isn't correct
7 Incorrect 365 ms 1092 KB Output isn't correct
8 Incorrect 430 ms 1188 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 2964 KB Output isn't correct
2 Incorrect 287 ms 3040 KB Output isn't correct
3 Incorrect 279 ms 3056 KB Output isn't correct
4 Incorrect 2 ms 3056 KB Output isn't correct
5 Incorrect 417 ms 5380 KB Output isn't correct
6 Incorrect 439 ms 5380 KB Output isn't correct
7 Incorrect 416 ms 5436 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 5436 KB Output isn't correct
2 Incorrect 76 ms 5436 KB Output isn't correct
3 Incorrect 154 ms 5436 KB Output isn't correct
4 Incorrect 131 ms 5436 KB Output isn't correct
5 Incorrect 152 ms 5436 KB Output isn't correct
6 Incorrect 354 ms 5436 KB Output isn't correct
7 Incorrect 285 ms 5436 KB Output isn't correct
8 Incorrect 162 ms 5436 KB Output isn't correct
9 Incorrect 1114 ms 6588 KB Output isn't correct
10 Incorrect 496 ms 6588 KB Output isn't correct
11 Incorrect 743 ms 6588 KB Output isn't correct
12 Incorrect 1099 ms 6588 KB Output isn't correct
13 Incorrect 1330 ms 6588 KB Output isn't correct