oj.uz

답안 #84049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84049 2018-11-12T13:59:04 Z aminra 케이크 (CEOI14_cake) C++14
0 / 100
 1648 ms 6460 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({tmp, idx});
			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);
				int L = s - 1, R = n;
				while(R - L > 1)
				{
					int mid = (L + R) >> 1;
					if(get(1, 0, n, s + 1, mid + 1) > mx)
						R = mid;
					else
						L = mid;
				}
				cout << R - idx - 1 << "\n";
			}
			else
			{
				int mx = get(1, 0, n, s + 1, idx + 1);
				int L = -1, R = s;
				while(R - L > 1)
				{
					int mid = (L + R) >> 1;
					if(get(1, 0, n, mid, s) > 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 678 ms 832 KB Output isn't correct
2 Correct 479 ms 832 KB Output is correct
3 Correct 536 ms 832 KB Output is correct
4 Correct 435 ms 836 KB Output is correct
5 Incorrect 754 ms 984 KB Output isn't correct
6 Correct 679 ms 1096 KB Output is correct
7 Correct 526 ms 1096 KB Output is correct
8 Correct 445 ms 1128 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 3052 KB Output is correct
2 Correct 255 ms 3052 KB Output is correct
3 Correct 248 ms 3052 KB Output is correct
4 Incorrect 3 ms 3052 KB Output isn't correct
5 Correct 399 ms 5548 KB Output is correct
6 Incorrect 417 ms 5548 KB Output isn't correct
7 Correct 347 ms 5548 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 5548 KB Output isn't correct
2 Correct 87 ms 5548 KB Output is correct
3 Correct 186 ms 5548 KB Output is correct
4 Correct 213 ms 5548 KB Output is correct
5 Incorrect 266 ms 5548 KB Output isn't correct
6 Correct 360 ms 5548 KB Output is correct
7 Correct 312 ms 5548 KB Output is correct
8 Correct 259 ms 5548 KB Output is correct
9 Incorrect 1588 ms 6428 KB Output isn't correct
10 Incorrect 844 ms 6428 KB Output isn't correct
11 Correct 1062 ms 6428 KB Output is correct
12 Correct 1501 ms 6428 KB Output is correct
13 Incorrect 1648 ms 6460 KB Output isn't correct