oj.uz

Submission #131891

# Submission time Handle Problem Language Result Execution time Memory
131891 2019-07-17T21:57:22 Z bogdan10bos Cake (CEOI14_cake) C++14
100 / 100
 1600 ms 8452 KB 
/// 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);
		}
	}
}

Compilation message

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.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 380 KB Output is correct
5 Correct 23 ms 760 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 764 KB Output is correct
2 Correct 502 ms 760 KB Output is correct
3 Correct 563 ms 760 KB Output is correct
4 Correct 474 ms 760 KB Output is correct
5 Correct 698 ms 1272 KB Output is correct
6 Correct 593 ms 1272 KB Output is correct
7 Correct 648 ms 1272 KB Output is correct
8 Correct 655 ms 1016 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4216 KB Output is correct
2 Correct 241 ms 3876 KB Output is correct
3 Correct 242 ms 3832 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 356 ms 7160 KB Output is correct
6 Correct 444 ms 7160 KB Output is correct
7 Correct 358 ms 6392 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 504 KB Output is correct
2 Correct 98 ms 636 KB Output is correct
3 Correct 246 ms 2212 KB Output is correct
4 Correct 194 ms 2168 KB Output is correct
5 Correct 211 ms 680 KB Output is correct
6 Correct 459 ms 2396 KB Output is correct
7 Correct 332 ms 1332 KB Output is correct
8 Correct 360 ms 3448 KB Output is correct
9 Correct 1600 ms 8312 KB Output is correct
10 Correct 699 ms 1444 KB Output is correct
11 Correct 882 ms 2684 KB Output is correct
12 Correct 1551 ms 8452 KB Output is correct
13 Correct 1580 ms 8312 KB Output is correct