oj.uz

Submission #546043

# Submission time Handle Problem Language Result Execution time Memory
546043 2022-04-06T07:09:46 Z blue Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 25880 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});

	int Q;
	cin >> Q;

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

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

			elements.erase({d[i], i});
			d[i] = ++ld;

			// cerr << "new di = " << 

			vector<pii> new_elements;
			new_elements.push_back({d[i], i});

			for(int f = 1; f <= e-1; f++)
			{
				auto x = *elements.rbegin();
				elements.erase(x);

				new_elements.push_back({++ld, x.second});
			}

			for(auto x : new_elements)
			{
				S.update(1, x.second, x.first);
				elements.insert(x);
			}
		}
		else
		{
			int b;
			cin >> b;

			vi nd(1+N+1);
			for(int i = 0; i <= N+1; i++)
			{
				nd[i] = S.rangemax(1, i, i);
			}

			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';
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 867 ms 13840 KB Output isn't correct
2 Incorrect 584 ms 1872 KB Output isn't correct
3 Incorrect 691 ms 6180 KB Output isn't correct
4 Correct 590 ms 1336 KB Output is correct
5 Incorrect 1431 ms 15264 KB Output isn't correct
6 Incorrect 1228 ms 13436 KB Output isn't correct
7 Incorrect 1030 ms 7692 KB Output isn't correct
8 Correct 1241 ms 2860 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 10448 KB Time limit exceeded
2 Execution timed out 2091 ms 10452 KB Time limit exceeded
3 Execution timed out 2095 ms 10452 KB Time limit exceeded
4 Incorrect 0 ms 212 KB Output isn't correct
5 Execution timed out 2083 ms 25748 KB Time limit exceeded
6 Execution timed out 2082 ms 25720 KB Time limit exceeded
7 Execution timed out 2085 ms 25880 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 992 KB Time limit exceeded
2 Execution timed out 2081 ms 964 KB Time limit exceeded
3 Execution timed out 2079 ms 5424 KB Time limit exceeded
4 Execution timed out 2085 ms 5416 KB Time limit exceeded
5 Execution timed out 2099 ms 908 KB Time limit exceeded
6 Execution timed out 2086 ms 6996 KB Time limit exceeded
7 Execution timed out 2088 ms 1356 KB Time limit exceeded
8 Execution timed out 2084 ms 10916 KB Time limit exceeded
9 Execution timed out 2047 ms 25720 KB Time limit exceeded
10 Execution timed out 2085 ms 1152 KB Time limit exceeded
11 Execution timed out 2073 ms 2260 KB Time limit exceeded
12 Execution timed out 2080 ms 20612 KB Time limit exceeded
13 Execution timed out 2085 ms 25732 KB Time limit exceeded