oj.uz

Submission #131888

# Submission time Handle Problem Language Result Execution time Memory
131888 2019-07-17T21:24:50 Z bogdan10bos Cake (CEOI14_cake) C++14
0 / 100
 1405 ms 8392 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)
	{
		ans = 1 << 30;
		pp = -1;
		Q(1, 1, N, st, dr);
		return pp;
	}

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

	pii jmkq(int st, int dr)
	{
		ans = 1 << 30;
		pp = -1;
		Q(1, 1, N, st, dr);
		return {ans, pp};
	}
}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, 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);
			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);
			aint.U(1, 1, N, 1, N, 1);
			for(int i = 10; i > e; i--)	pos[i] = pos[i - 1];
			pos[e] = p;
			for(int i = 1; i <= e; i++)
				aint.U(1, 1, N, pos[i], i);
		}
	}
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 345 ms 888 KB Output isn't correct
2 Incorrect 233 ms 760 KB Output isn't correct
3 Correct 252 ms 768 KB Output is correct
4 Correct 162 ms 760 KB Output is correct
5 Incorrect 368 ms 1140 KB Output isn't correct
6 Incorrect 283 ms 1144 KB Output isn't correct
7 Correct 275 ms 1144 KB Output is correct
8 Correct 173 ms 1144 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 4112 KB Output is correct
2 Incorrect 250 ms 3848 KB Output isn't correct
3 Incorrect 217 ms 3768 KB Output isn't correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 Correct 338 ms 7296 KB Output is correct
6 Incorrect 435 ms 7288 KB Output isn't correct
7 Incorrect 333 ms 6796 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 504 KB Output isn't correct
2 Incorrect 78 ms 632 KB Output isn't correct
3 Incorrect 191 ms 2168 KB Output isn't correct
4 Incorrect 167 ms 2236 KB Output isn't correct
5 Incorrect 192 ms 744 KB Output isn't correct
6 Incorrect 322 ms 2424 KB Output isn't correct
7 Incorrect 230 ms 1272 KB Output isn't correct
8 Correct 162 ms 3448 KB Output is correct
9 Incorrect 1369 ms 8336 KB Output isn't correct
10 Incorrect 591 ms 1504 KB Output isn't correct
11 Incorrect 739 ms 2424 KB Output isn't correct
12 Correct 1267 ms 8272 KB Output is correct
13 Incorrect 1405 ms 8392 KB Output isn't correct