oj.uz

Submission #546064

# Submission time Handle Problem Language Result Execution time Memory
546064 2022-04-06T08:01:43 Z blue Cake (CEOI14_cake) C++17
0 / 100
 1290 ms 32620 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;
			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;
			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\n";
				int rmx = S.rangemax(1, a+1, b);
				// 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 = S.rangemax(1, b, 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 730 ms 13908 KB Output isn't correct
2 Correct 331 ms 1836 KB Output is correct
3 Correct 437 ms 6132 KB Output is correct
4 Correct 204 ms 1312 KB Output is correct
5 Incorrect 725 ms 15132 KB Output isn't correct
6 Incorrect 635 ms 13232 KB Output isn't correct
7 Correct 473 ms 7476 KB Output is correct
8 Correct 241 ms 2772 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 10572 KB Output isn't correct
2 Incorrect 85 ms 10556 KB Output isn't correct
3 Correct 77 ms 10408 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 220 ms 25420 KB Output is correct
6 Incorrect 220 ms 25596 KB Output isn't correct
7 Incorrect 118 ms 24956 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 1340 KB Output isn't correct
2 Incorrect 42 ms 1108 KB Output isn't correct
3 Incorrect 102 ms 5508 KB Output isn't correct
4 Incorrect 155 ms 5656 KB Output isn't correct
5 Incorrect 180 ms 2952 KB Output isn't correct
6 Incorrect 188 ms 7484 KB Output isn't correct
7 Correct 168 ms 2828 KB Output is correct
8 Correct 251 ms 11816 KB Output is correct
9 Incorrect 1290 ms 29224 KB Output isn't correct
10 Incorrect 629 ms 9068 KB Output isn't correct
11 Incorrect 797 ms 10244 KB Output isn't correct
12 Correct 1253 ms 24660 KB Output is correct
13 Incorrect 870 ms 32620 KB Output isn't correct