oj.uz

Submission #546045

# Submission time Handle Problem Language Result Execution time Memory
546045 2022-04-06T07:13:43 Z blue Cake (CEOI14_cake) C++17
15 / 100
 2000 ms 26804 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

int N;
vi d;

struct segtree
{
	int Z;
	vi l, r, mxv;

	void build(int i, int L, int R)
	{
		// cerr << "build " << i << ' ' << L << ' ' << R << '\n';
		l[i] = L;
		r[i] = R;
		if(l[i] == r[i])
		{
			// cerr << "case 1\n";
			mxv[i] = d[l[i]];
		}
		else
		{
			// cerr << "case 2\n";
			build(2*i, L, (L+R)/2);
			build(2*i+1, (L+R)/2+1, R);
			mxv[i] = max(mxv[2*i], mxv[2*i+1]);
		}
		// cerr << i << " -> " <<  l[i] << ' ' << r[i] << " : " << mxv[i] << '\n';
		// cerr << "exit\n";
	}

	segtree()
	{
		Z = 4*(1+N+1);
		l = r = mxv = vi(1 + Z);

		build(1, 0, N+1);
	}

	void update(int i, int p, int v)
	{
		if(l[i] == r[i]) mxv[i] = v;
		else 
		{
			if(p <= (l[i] + r[i])/2) update(2*i, p, v);
			else update(2*i+1, p, v);

			mxv[i] = max(mxv[2*i], mxv[2*i+1]);
		}
	}

	int rangemax(int i, int L, int R)
	{
		// cerr << "rangemax : " << i << ' ' << l[i] << ' ' << r[i] << " <> " << L << ' ' << R << '\n';
		if(R < l[i] || r[i] < L) return -1'000'000'000;
		else if(L <= l[i] && r[i] <= R) return mxv[i];
		else return max(rangemax(2*i, L, R), rangemax(2*i+1, L, R));
	}

	int locatenextgeq(int p, int v)
	{
		int i = 1;
		while(l[i] != r[i])
		{
			if(p <= (l[i] + r[i])/2)
				i = 2*i;
			else
				i = 2*i + 1;
		}

		while(!(l[i] != r[i] && mxv[2*i+1] >= v))
			i /= 2;

		i = 2*i + 1;

		while(l[i] != r[i])
		{
			if(mxv[2*i] >= v)
				i = 2*i;
			else
				i = 2*i + 1;
		}

		return l[i];
	}

	int locateprevgeq(int p, int v)
	{
		int i = 1;
		while(l[i] != r[i])
		{
			if(p <= (l[i] + r[i])/2)
				i = 2*i;
			else
				i = 2*i + 1;
		}

		// cerr << "positional i = " << i << '\n';

		while(!(l[i] != r[i] && mxv[2*i] >= v))
		{
			i /= 2;
			// cerr << i << ' ' << l[i] << ' ' << r[i] << " : " << mxv[2*i] << '\n';

			if(i == 0) while(1);
		}

		i = 2*i;
		
		// cerr << "resulting i = " << i << '\n';

		while(l[i] != r[i])
		{
			if(mxv[2*i + 1] >= v)
				i = 2*i + 1;
			else
				i = 2*i;
		}

		return l[i];
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int a;

	cin >> N >> a;

	d = vi(1+N+1);
	for(int i = 1; i <= N; i++) cin >> d[i];
	d[0] = d[N+1] = 1'000'000'000;

	int ld = N+1;

	segtree S;

	// cerr << "done\n";

	set<pii> elements;
	for(int i = 1; i <= N; i++)
		elements.insert({d[i], i});


	vi delpos(1+N);
	for(int i = 1; i <= N; i++)
		delpos[d[i]] = i;

	int Q;
	cin >> Q;

	for(int j = 1; j <= Q; j++)
	{
		char c;
		cin >> c;

		if(c == 'E')
		{
			int i, e;
			cin >> i >> e;

			while(delpos[N-e+1] != i)
			{
				int di = d[i];

				int pi = delpos[d[i] + 1];
				int dpi = d[pi];

				swap(d[i], d[pi]);
				swap(delpos[di], delpos[dpi]);
			}
		}
		else
		{
			int b;
			cin >> b;

			vi nd(1+N+1);
			for(int i = 1; i <= N; i++)
			{
				nd[delpos[i]] = i;
			}
			nd[0] = nd[N+1] = 1'000'000'000;

			int res = 0;

			int x = a,y = a;
			while(!(x <= b && b <= y))
			{
				if(nd[x-1] < nd[y+1])
				{
					x -= 1;
				}
				else
				{
					y += 1;
				}

				res++;
			}

			cout << res << '\n';
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:146:6: warning: unused variable 'ld' [-Wunused-variable]
  146 |  int ld = N+1;
      |      ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 27 ms 476 KB Output is correct
5 Correct 584 ms 1520 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 1252 KB Time limit exceeded
2 Correct 676 ms 1388 KB Output is correct
3 Execution timed out 2089 ms 1368 KB Time limit exceeded
4 Correct 96 ms 1380 KB Output is correct
5 Execution timed out 2090 ms 2828 KB Time limit exceeded
6 Execution timed out 2087 ms 2900 KB Time limit exceeded
7 Execution timed out 2089 ms 2872 KB Time limit exceeded
8 Correct 127 ms 2956 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 11032 KB Time limit exceeded
2 Execution timed out 2080 ms 11020 KB Time limit exceeded
3 Execution timed out 2084 ms 10908 KB Time limit exceeded
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2078 ms 26752 KB Time limit exceeded
6 Execution timed out 2080 ms 26804 KB Time limit exceeded
7 Execution timed out 2096 ms 26744 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 720 KB Output is correct
2 Correct 1344 ms 1224 KB Output is correct
3 Execution timed out 2083 ms 5620 KB Time limit exceeded
4 Execution timed out 2087 ms 5620 KB Time limit exceeded
5 Correct 1554 ms 1020 KB Output is correct
6 Execution timed out 2070 ms 7380 KB Time limit exceeded
7 Execution timed out 2084 ms 1664 KB Time limit exceeded
8 Execution timed out 2093 ms 10960 KB Time limit exceeded
9 Execution timed out 2092 ms 26744 KB Time limit exceeded
10 Execution timed out 2084 ms 1016 KB Time limit exceeded
11 Execution timed out 2075 ms 2724 KB Time limit exceeded
12 Execution timed out 2088 ms 21464 KB Time limit exceeded
13 Execution timed out 2097 ms 26740 KB Time limit exceeded