oj.uz

답안 #62741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62741 2018-07-30T00:13:33 Z MatheusLealV 케이크 (CEOI14_cake) C++17
73.3333 / 100
 2000 ms 14604 KB 
#include <bits/stdc++.h>
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
#define N 250050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, q, a, v[N], dx[N], soma, tree[4*N];

vector<int> best;

vector<pii> ini;

void upd(int nod, int a, int b, int i, int x)
{
	if(a == b) tree[nod] = x;

	else
	{
		if(i <= mid) upd(l, a, mid, i, x);

		else upd(r, mid + 1, b, i, x);

		tree[nod] = max(tree[l], tree[r]);
	}
}

int query(int nod, int a, int b, int i, int j)
{
	if(j < a or i > b) return 0;

	if(i <= a and j >= b) return tree[nod];

	return max(query(l, a, mid, i, j), query(r, mid + 1, b, i, j));
}

int findR(int nod, int a, int b, int i, int val)
{
	if(tree[nod] <= val or b <= i) return -1;

	if(a == b) return a;

	if(tree[l] > val)
	{
		int k = findR(l, a, mid, i, val);

		if(k >= 0) return k;
	}

	return findR(r, mid + 1, b, i, val);
}

int findL(int nod, int a, int b, int i, int val)
{
	if(tree[nod] <= val or a >= i) return -1;

	if(a == b) return a;

	if(tree[r] > val)
	{
		int k = findL(r, mid + 1, b, i, val);

		if(k >= 0) return k;
	}

	return findL(l, a, mid, i, val);
}

void add(int x, int k)
{
	vector<int> aux;

	int id = 0;

	for(int i = 0; ;i++)
	{
		id = i;

		if(aux.size() == k - 1 or i >= best.size()) break;

		if(best[i] != x) aux.push_back(best[i]);
	}

	aux.push_back(x);

	for(int j = id; j < min(15, (int)best.size()); j++)
		if(best[j] != x) aux.push_back(best[j]);

	best = aux;

	for(int i = best.size() - 2; i >= 0; i--)
	{
		dx[best[i]] = dx[best[i + 1]] + 1;

		upd(1, 0, n, best[i], dx[best[i]]);
	}
}

void print()
{
	for(auto x: best) cout<<x<<" ";

	cout<<"\n";
}

int main()
{
	//ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>a;

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		ini.push_back({-v[i], i}), dx[i] = v[i];

		upd(1, 0, n, i, v[i]);
	}

	sort(ini.begin(), ini.end());

	for(int i = 0; i < min(15, (int) ini.size()); i++) best.push_back(ini[i].s);

	best.push_back(0);

	cin>>q;

	for(int i = 0; i < q; i++)
	{
		char c; int x, y;

		cin>>c>>x;

		if(c == 'E')
		{
			cin>>y;

			add(x, y);
		}

		else
		{
			if(a == x)
			{
				cout<<"0\n";

				continue;
			}

			if(x < a)
			{
				int maior = query(1, 0, n, x, a - 1);

				int R = findR(1, 0, n, a, maior);

				if(R == -1) R = n + 1;

				int ans = (a - x) + (R - a) - 1;

				cout<<ans<<"\n";
			}

			else
			{
				int ans = x - a;

				int maior = query(1, 0, n, a + 1, x);

				for(int j = a - 1; j >= 1; j--)
				{
					if(dx[j] > maior) break;

					ans ++;
				}

				cout<<ans<<"\n";
			}
		}
		
	}
}

Compilation message

cake.cpp: In function 'void add(int, int)':
cake.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(aux.size() == k - 1 or i >= best.size()) break;
      ~~~~~~~~~~~^~~~~~~~
cake.cpp:82:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(aux.size() == k - 1 or i >= best.size()) break;
                             ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 360 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 19 ms 656 KB Output is correct
5 Correct 61 ms 1132 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1386 ms 4744 KB Output is correct
2 Correct 1207 ms 4776 KB Output is correct
3 Correct 1262 ms 4848 KB Output is correct
4 Correct 1233 ms 4848 KB Output is correct
5 Correct 1206 ms 5216 KB Output is correct
6 Correct 1261 ms 5216 KB Output is correct
7 Correct 1311 ms 5216 KB Output is correct
8 Correct 1145 ms 5308 KB Output is correct

Subtask #3
10.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 861 ms 8036 KB Output is correct
2 Correct 1265 ms 8036 KB Output is correct
3 Correct 868 ms 8080 KB Output is correct
4 Correct 3 ms 8080 KB Output is correct
5 Execution timed out 2051 ms 11356 KB Time limit exceeded
6 Correct 714 ms 12388 KB Output is correct
7 Execution timed out 2039 ms 12388 KB Time limit exceeded

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 12388 KB Output is correct
2 Correct 168 ms 12388 KB Output is correct
3 Correct 572 ms 12388 KB Output is correct
4 Correct 633 ms 12388 KB Output is correct
5 Correct 551 ms 12388 KB Output is correct
6 Correct 661 ms 12388 KB Output is correct
7 Correct 635 ms 12388 KB Output is correct
8 Correct 746 ms 12388 KB Output is correct
9 Execution timed out 2051 ms 12976 KB Time limit exceeded
10 Correct 1159 ms 12976 KB Output is correct
11 Correct 1360 ms 12976 KB Output is correct
12 Execution timed out 2069 ms 13796 KB Time limit exceeded
13 Execution timed out 2059 ms 14604 KB Time limit exceeded