oj.uz

답안 #160496

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

using namespace std;

typedef long long ll;

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};
	}

	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+1;
			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)
			{
				ll 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:126: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:139:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:164:9: warning: unused variable 'p' [-Wunused-variable]
     int p = pos[M], last = findR(1, 1, n, A+1, M);
         ^
cake.cpp:174:9: warning: unused variable 'p' [-Wunused-variable]
     int p = pos[M], last = findL(1, 1, n, A-1, M);
         ^
cake.cpp:94: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:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &op);
   ~~~~~^~~~~~~~~~~~
cake.cpp:117: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:158: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 376 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 1955 ms 28668 KB Output isn't correct
2 Correct 1880 ms 28792 KB Output is correct
3 Correct 1915 ms 28656 KB Output is correct
4 Correct 1896 ms 28648 KB Output is correct
5 Execution timed out 2060 ms 29304 KB Time limit exceeded
6 Correct 1978 ms 29536 KB Output is correct
7 Execution timed out 2019 ms 29440 KB Time limit exceeded
8 Correct 1990 ms 29648 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 4508 KB Output is correct
2 Correct 91 ms 4344 KB Output is correct
3 Correct 83 ms 4344 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 142 ms 8444 KB Output is correct
6 Incorrect 167 ms 8568 KB Output isn't correct
7 Correct 121 ms 8220 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 2172 KB Output isn't correct
2 Correct 94 ms 2428 KB Output is correct
3 Correct 184 ms 4344 KB Output is correct
4 Correct 193 ms 4396 KB Output is correct
5 Incorrect 321 ms 5384 KB Output isn't correct
6 Correct 379 ms 7416 KB Output is correct
7 Correct 436 ms 7416 KB Output is correct
8 Correct 862 ms 14456 KB Output is correct
9 Incorrect 1568 ms 25288 KB Output isn't correct
10 Incorrect 1153 ms 17020 KB Output isn't correct
11 Correct 1451 ms 18424 KB Output is correct
12 Correct 1604 ms 24132 KB Output is correct
13 Incorrect 1431 ms 25400 KB Output isn't correct