oj.uz

Submission #84039

# Submission time Handle Problem Language Result Execution time Memory
84039 2018-11-12T13:14:24 Z aminra Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 5620 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();
			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({lrg[j].second, ++cur}), del.push_back({lrg[j].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";
			}
		}
	}
}

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 Execution timed out 2047 ms 1184 KB Time limit exceeded
2 Execution timed out 2069 ms 1184 KB Time limit exceeded
3 Execution timed out 2064 ms 1224 KB Time limit exceeded
4 Incorrect 410 ms 1224 KB Output isn't correct
5 Execution timed out 2065 ms 1612 KB Time limit exceeded
6 Execution timed out 2063 ms 1612 KB Time limit exceeded
7 Execution timed out 2059 ms 1792 KB Time limit exceeded
8 Incorrect 429 ms 1792 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 439 ms 3168 KB Output isn't correct
2 Incorrect 325 ms 3244 KB Output isn't correct
3 Incorrect 293 ms 3244 KB Output isn't correct
4 Incorrect 2 ms 3244 KB Output isn't correct
5 Incorrect 461 ms 5292 KB Output isn't correct
6 Incorrect 526 ms 5444 KB Output isn't correct
7 Incorrect 482 ms 5444 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 5444 KB Time limit exceeded
2 Execution timed out 2055 ms 5444 KB Time limit exceeded
3 Execution timed out 2074 ms 5444 KB Time limit exceeded
4 Execution timed out 2068 ms 5444 KB Time limit exceeded
5 Execution timed out 2062 ms 5444 KB Time limit exceeded
6 Execution timed out 2068 ms 5444 KB Time limit exceeded
7 Execution timed out 2062 ms 5444 KB Time limit exceeded
8 Execution timed out 2076 ms 5444 KB Time limit exceeded
9 Execution timed out 2069 ms 5620 KB Time limit exceeded
10 Execution timed out 2071 ms 5620 KB Time limit exceeded
11 Execution timed out 2063 ms 5620 KB Time limit exceeded
12 Execution timed out 2057 ms 5620 KB Time limit exceeded
13 Execution timed out 2058 ms 5620 KB Time limit exceeded