oj.uz

Submission #160578

# Submission time Handle Problem Language Result Execution time Memory
160578 2019-10-28T15:03:28 Z luciocf Cake (CEOI14_cake) C++14
100 / 100
 978 ms 13704 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

int n;
int a[maxn];

pair<int, int> aux[maxn];

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;

			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++)
				if (mx[i].second != ind)
					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-1].first+1;
					mx[i].first = mx[i-1].first+1;
				}
			}

			for (int i = 0; i < mx.size(); i++)
			{
				a[mx[i].second] = mx[i].first;
				upd(1, 1, n, mx[i].second, mx[i].first);
			}
		}
		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 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 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:119: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:133:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:142:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:90: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:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &op);
   ~~~~~^~~~~~~~~~~~
cake.cpp:113: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:151:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ind);
    ~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 17 ms 800 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 5112 KB Output is correct
2 Correct 790 ms 4976 KB Output is correct
3 Correct 839 ms 4972 KB Output is correct
4 Correct 743 ms 4984 KB Output is correct
5 Correct 937 ms 5628 KB Output is correct
6 Correct 869 ms 5880 KB Output is correct
7 Correct 894 ms 5692 KB Output is correct
8 Correct 789 ms 5944 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 4488 KB Output is correct
2 Correct 91 ms 4340 KB Output is correct
3 Correct 84 ms 4344 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 146 ms 8420 KB Output is correct
6 Correct 145 ms 8488 KB Output is correct
7 Correct 120 ms 8300 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1016 KB Output is correct
2 Correct 66 ms 1020 KB Output is correct
3 Correct 139 ms 2688 KB Output is correct
4 Correct 121 ms 2580 KB Output is correct
5 Correct 208 ms 1788 KB Output is correct
6 Correct 244 ms 3836 KB Output is correct
7 Correct 249 ms 2680 KB Output is correct
8 Correct 468 ms 5112 KB Output is correct
9 Correct 978 ms 13348 KB Output is correct
10 Correct 575 ms 5348 KB Output is correct
11 Correct 662 ms 6528 KB Output is correct
12 Correct 932 ms 12460 KB Output is correct
13 Correct 860 ms 13704 KB Output is correct