제출 #131891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131891		bogdan10bos	케이크 (CEOI14_cake)	C++14	100 / 100	1600 ms	8452 KiB

cake

/// Ce plm inseamna "acasa"? (nu buc in plm)
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int NMAX = 250005;

int N, A;
int pos[15];

class SegmentTree
{
public:
	int ans, pp;
	int aint[4 * NMAX], add[4 * NMAX], pos[4 * NMAX];

	void lazy(int nod, int st, int mij, int dr)
	{
		if(add[nod] == 0)	return;
		aint[nod * 2] += add[nod];
		aint[nod * 2 + 1] += add[nod];
		add[nod * 2] += add[nod];
		add[nod * 2 + 1] += add[nod];
		add[nod] = 0;
	}

	void U(int nod, int st, int dr, int pp, int val)
	{
		if(st == dr)
		{
			aint[nod] = val;
			add[nod] = 0;
			pos[nod] = st;
			return;
		}

		int mij = st + (dr - st) / 2;
		lazy(nod, st, mij, dr);

		if(pp <= mij)	U(nod * 2, st, mij, pp, val);
		else	U(nod * 2 + 1, mij + 1, dr, pp, val);

		aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
		if(aint[nod] == aint[nod * 2])	pos[nod] = pos[nod * 2];
		else	pos[nod] = pos[nod * 2 + 1];
	}

	void U(int nod, int st, int dr, int sti, int dri, int val)
	{
		if(sti <= st && dr <= dri)
		{
			aint[nod] += val;
			add[nod] += val;
			return;
		}

		int mij = st + (dr - st) / 2;
		lazy(nod, st, mij, dr);

		if(sti <= mij)	U(nod * 2, st, mij, sti, dri, val);
		if(mij < dri) U(nod * 2 + 1, mij + 1, dr, sti, dri, val);

		aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
		if(aint[nod] == aint[nod * 2])	pos[nod] = pos[nod * 2];
		else	pos[nod] = pos[nod * 2 + 1];
	}

	void Q(int nod, int st, int dr, int sti, int dri)
	{
		if(sti <= st && dr <= dri)
		{
			if(ans > aint[nod])
			{
				ans = aint[nod];
				pp = pos[nod];
			}
			return;
		}

		int mij = st + (dr - st) / 2;
		lazy(nod, st, mij, dr);

		if(sti <= mij)	Q(nod * 2, st, mij, sti, dri);
		if(mij < dri) Q(nod * 2 + 1, mij + 1, dr, sti, dri);
	}

	int query(int st, int dr)
	{
		if(st > dr)	return st;
		ans = 1 << 30;
		pp = -1;
		Q(1, 1, N, st, dr);
		return pp;
	}

	int qmin(int st, int dr)
	{
		if(st > dr)	return (1 << 30);
		ans = 1 << 30;
		pp = -1;
		Q(1, 1, N, st, dr);
		return ans;
	}
}aint;

void solve(int p)
{
	if(p == A)
	{
		printf("0\n");
		return;
	}
	int P = p;

	if(p < A)
	{
		int myp = aint.query(P, A - 1);
		int val = aint.qmin(myp, myp);
		int p = A + 1, u = N;
		int pp = A;
		while(p <= u)
		{
			int mij = p + (u - p) / 2;
			int q = aint.qmin(A + 1, mij);
			if(q > val)
			{
				pp = mij;
				p = mij + 1;
			}
			else
				u = mij - 1;
		}
		int ans = pp - P;
		printf("%d\n", ans);
		return;
	}

	if(p > A)
	{
		int myp = aint.query(A + 1, P);
		int val = aint.qmin(myp, myp);
		int p = 1, u = A - 1;
		int pp = A;
		while(p <= u)
		{
			int mij = p + (u - p) / 2;
			int q = aint.qmin(mij, A - 1);
			if(q > val)
			{
				pp = mij;
				u = mij - 1;
			}
			else
				p = mij + 1;
		}
		int ans = P - pp;
		printf("%d\n", ans);
		return;
	}
}

int main()
{
	//freopen("1.in", "r", stdin);
	scanf("%d%d", &N, &A);
	for(int i = 1; i <= N; i++)
	{
		int x;
		scanf("%d", &x);
		x = N - x + 1;
		if(x <= 10)	pos[x] = i;
		aint.U(1, 1, N, i, x);
	}
	int Q;
	scanf("%d", &Q);
	for(int q = 1; q <= Q; q++)
	{
		char ch = getchar();
		while(ch != 'F' && ch != 'E')	ch = getchar();

		if(ch == 'F')
		{
			int p;
			scanf("%d", &p);
			solve(p);
		}
		else if(ch == 'E')
		{
			int p, e;
			scanf("%d%d", &p, &e);

			int nowp = 11;
			for(int i = 1; i <= 10; i++)
				if(pos[i] == p)	nowp = i;
			if(nowp == 11) aint.U(1, 1, N, 1, N, 1), nowp = 10;

			for(int i = nowp; i > e; i--)	pos[i] = pos[i - 1];
			pos[e] = p;
			for(int i = 1; i <= 10 && i <= N; i++)
				aint.U(1, 1, N, pos[i], i);
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In function 'int main()':
cake.cpp:167: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:171:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
cake.cpp:177:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
cake.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
cake.cpp:192:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &p, &e);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50