oj.uz

Submission #546065

# Submission time Handle Problem Language Result Execution time Memory
546065 2022-04-06T08:09:26 Z blue Cake (CEOI14_cake) C++17
0 / 100
 1363 ms 32716 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;
		}

		if(mxv[i] >= v) return l[i];

		int rp = 1;

		while(!(rp && l[i] != r[i] && mxv[2*i+1] >= v))
		{
			if((i & 1) == 0)
				rp = 1;
			else
				rp = 0;
			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;
		}

		if(mxv[i] >= v) return l[i];

		// cerr << "positional i = " << i << '\n';
		// cerr << l[i] << ' ' << r[i] << ' ' << mxv[i] << '\n';

		int lp = 0;

		while(!(lp && l[i] != r[i] && mxv[2*i] >= v))
		{
			if(i & 1) lp = 1;
			else lp = 0;
			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';
		// cerr << l[i] << ' ' << r[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 i = 1; i <= N; i++) cerr << S.rangemax(1, i, i) << ' ';
	// 			cerr << '\n';

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

			int nld = ld + e-1;

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

				new_elements.push_back({nld - (f-1), x.second});
			}

			ld = nld + 1;

			for(auto x : new_elements)
			{
				S.update(1, x.second, x.first);
				elements.insert(x);
			}

			// for(int i = 1; i <= N; i++) cerr << S.rangemax(1, i, i) << ' ';
			// 	cerr << '\n';
		}
		else
		{
			int b;
			cin >> b;

			if(a == b)
			{
				cout << 0 << '\n';
				continue;
			}

			if(a <= b)
			{
				// cerr << "hello " << a << ' ' << b << " \n";
				int rmx = max(S.rangemax(1, a+1, b), d[a-1]);;
				// cerr << "rmx = " << rmx << '\n';
				// cerr << "a-1 = " << a-1 << '\n';
				int prvp = S.locateprevgeq(a-1, rmx+1);
				// cerr << "prvp = " << prvp << '\n';

				cout << b - prvp - 1 << '\n';
			}
			else
			{
				// cerr << "!\n";
				int rmx = max(S.rangemax(1, b, a-1), d[a+1]);
				// cerr << "rmx = " << rmx << '\n';
				int nxtp = S.locatenextgeq(a+1, rmx+1);
				// cerr << "nxtp = " << nxtp << '\n';

				cout << nxtp - b - 1 << '\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 651 ms 13924 KB Output isn't correct
2 Incorrect 342 ms 1748 KB Output isn't correct
3 Correct 454 ms 6124 KB Output is correct
4 Incorrect 186 ms 1236 KB Output isn't correct
5 Incorrect 767 ms 15176 KB Output isn't correct
6 Incorrect 598 ms 13272 KB Output isn't correct
7 Correct 450 ms 7528 KB Output is correct
8 Incorrect 234 ms 2772 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 147 ms 10628 KB Output isn't correct
2 Incorrect 86 ms 10568 KB Output isn't correct
3 Incorrect 78 ms 10548 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 263 ms 25328 KB Output is correct
6 Incorrect 215 ms 25472 KB Output isn't correct
7 Incorrect 122 ms 25368 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 1328 KB Output isn't correct
2 Incorrect 43 ms 1112 KB Output isn't correct
3 Incorrect 96 ms 5516 KB Output isn't correct
4 Incorrect 144 ms 5724 KB Output isn't correct
5 Incorrect 204 ms 2984 KB Output isn't correct
6 Incorrect 211 ms 7516 KB Output isn't correct
7 Incorrect 163 ms 2736 KB Output isn't correct
8 Correct 253 ms 11784 KB Output is correct
9 Incorrect 1363 ms 29216 KB Output isn't correct
10 Incorrect 635 ms 8984 KB Output isn't correct
11 Incorrect 884 ms 10296 KB Output isn't correct
12 Incorrect 1306 ms 24524 KB Output isn't correct
13 Incorrect 896 ms 32716 KB Output isn't correct