oj.uz

답안 #160497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160497 2019-10-28T04:08:44 Z luciocf 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 31224 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

int n;
int a[maxn];

pair<int, int> aux[maxn];

map<int, int> pos;

int tree[4*maxn];

vector<pair<int, int>> mx;

void faz(void)
{
	sort(aux+1, aux+n+1);

	for (int i = max(1, n-12); i <= n; i++)
		mx.push_back({a[aux[i].second], aux[i].second});
}

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = a[l];
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

void upd(int node, int l, int r, int pos, int v)
{
	if (l == r)
	{
		tree[node] = v;
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

int query(int node, int l, int r, int a, int b)
{
	if (l > b || r < a) return -1;
	if (l >= a && r <= b) return tree[node];

	int mid = (l+r)>>1;

	return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}

int findL(int node, int l, int r, int pos, int v)
{
	if (l > pos || tree[node] <= v) return -1;
	if (l == r) return l;

	int mid = (l+r)>>1;

	int p1 = findL(2*node+1, mid+1, r, pos, v);
	return (p1 == -1 ? findL(2*node, l, mid, pos, v) : p1);
}

int findR(int node, int l, int r, int pos, int v)
{
	if (r < pos || tree[node] <= v) return -1;
	if (l == r) return l;

	int mid = (l+r)>>1;

	int p1 = findR(2*node, l, mid, pos, v);
	return (p1 == -1 ? findR(2*node+1, mid+1, r, pos, v) : p1);
}

int main(void)
{
	int A;
	scanf("%d %d", &n, &A);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		aux[i] = {a[i], i}, pos[a[i]] = i;
	}

	faz();

	build(1, 1, n);

	int q;
	scanf("%d", &q);

	for (int t = 1; t <= q; t++)
	{
		char op;
		scanf(" %c", &op);

		if (op == 'E')
		{
			int ind, e;
			scanf("%d %d", &ind, &e);

			vector<pair<int, int>> aux;

			a[ind] = mx[mx.size()-e].first;
			pos[a[ind]] = ind;

			int qtd = 0;

			for (int i = mx.size()-1; i > mx.size()-e; i--, qtd++)
				aux.push_back(mx[i]);

			aux.push_back({a[ind], ind}), ++qtd;

			for (int i = mx.size()-e; i >= 0 && qtd < 13; i--, qtd++)
				aux.push_back(mx[i]);

			mx.clear();

			for (int i = aux.size()-1; i >= 0; i--)
				mx.push_back(aux[i]);

			for (int i = 1; i < mx.size(); i++)
			{
				if (mx[i].first == mx[i-1].first)
				{
					a[mx[i].second]++;
					mx[i].first++;
				}
			}

			for (int i = 0; i < mx.size(); i++)
			{
				upd(1, 1, n, mx[i].second, mx[i].first);
				pos[mx[i].first] = mx[i].second;
			}

		}
		else
		{
			int ind;
			scanf("%d", &ind);

			if (ind == A) printf("0\n");
			else if (ind < A)
			{
				int M = query(1, 1, n, ind, A-1);
				int p = pos[M], last = findR(1, 1, n, A+1, M);

				if (last == -1)
					printf("%d\n", n-ind);
				else
					printf("%d\n", last-ind-1);
			}
			else
			{
				int M = query(1, 1, n, A+1, ind);
				int p = pos[M], last = findL(1, 1, n, A-1, M);

				if (last == -1)
					printf("%d\n", ind-1);
				else
					printf("%d\n", ind-last-1);
			}
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:124:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = mx.size()-1; i > mx.size()-e; i--, qtd++)
                              ~~^~~~~~~~~~~~~
cake.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:146:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:162:9: warning: unused variable 'p' [-Wunused-variable]
     int p = pos[M], last = findR(1, 1, n, A+1, M);
         ^
cake.cpp:172:9: warning: unused variable 'p' [-Wunused-variable]
     int p = pos[M], last = findL(1, 1, n, A-1, M);
         ^
cake.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &A);
  ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &op);
   ~~~~~^~~~~~~~~~~~
cake.cpp:115:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &e);
    ~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:156:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ind);
    ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1957 ms 25320 KB Output isn't correct
2 Correct 1913 ms 25336 KB Output is correct
3 Correct 1953 ms 25464 KB Output is correct
4 Execution timed out 2051 ms 25388 KB Time limit exceeded
5 Execution timed out 2076 ms 26332 KB Time limit exceeded
6 Execution timed out 2043 ms 26352 KB Time limit exceeded
7 Execution timed out 2031 ms 26144 KB Time limit exceeded
8 Execution timed out 2032 ms 26388 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 8312 KB Output is correct
2 Correct 146 ms 8184 KB Output is correct
3 Correct 140 ms 8200 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 357 ms 18404 KB Output is correct
6 Incorrect 351 ms 18420 KB Output isn't correct
7 Correct 223 ms 18168 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 2240 KB Output isn't correct
2 Correct 97 ms 2396 KB Output is correct
3 Correct 207 ms 6264 KB Output is correct
4 Correct 239 ms 6280 KB Output is correct
5 Incorrect 309 ms 4952 KB Output isn't correct
6 Correct 416 ms 9292 KB Output is correct
7 Correct 451 ms 6872 KB Output is correct
8 Correct 914 ms 17164 KB Output is correct
9 Incorrect 1771 ms 31128 KB Output isn't correct
10 Incorrect 1169 ms 14072 KB Output isn't correct
11 Correct 1257 ms 15632 KB Output is correct
12 Correct 1675 ms 28124 KB Output is correct
13 Incorrect 1665 ms 31224 KB Output isn't correct