oj.uz

Submission #546059

# Submission time Handle Problem Language Result Execution time Memory
546059 2022-04-06T07:43:02 Z blue Cake (CEOI14_cake) C++17
0 / 100
 1256 ms 32712 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];

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

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

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

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

			// 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, b);
				int prvp = S.locateprevgeq(a-1, rmx+1);

				cout << b - prvp - 1 << '\n';
			}
			else
			{
				// cerr << "!\n";
				int rmx = S.rangemax(1, b, a);
				// 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 1 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 676 ms 13948 KB Output isn't correct
2 Incorrect 323 ms 1976 KB Output isn't correct
3 Incorrect 413 ms 6316 KB Output isn't correct
4 Correct 210 ms 1428 KB Output is correct
5 Incorrect 711 ms 15280 KB Output isn't correct
6 Incorrect 602 ms 13440 KB Output isn't correct
7 Incorrect 439 ms 7628 KB Output isn't correct
8 Correct 239 ms 2900 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 10824 KB Output isn't correct
2 Incorrect 83 ms 10700 KB Output isn't correct
3 Incorrect 83 ms 10552 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 234 ms 25488 KB Output isn't correct
6 Incorrect 201 ms 25460 KB Output isn't correct
7 Incorrect 110 ms 25184 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 1396 KB Output isn't correct
2 Incorrect 47 ms 1212 KB Output isn't correct
3 Incorrect 123 ms 5668 KB Output isn't correct
4 Incorrect 135 ms 5876 KB Output isn't correct
5 Incorrect 176 ms 3128 KB Output isn't correct
6 Incorrect 198 ms 7636 KB Output isn't correct
7 Incorrect 166 ms 2984 KB Output isn't correct
8 Incorrect 249 ms 11928 KB Output isn't correct
9 Incorrect 1256 ms 29456 KB Output isn't correct
10 Incorrect 612 ms 9224 KB Output isn't correct
11 Incorrect 785 ms 10436 KB Output isn't correct
12 Incorrect 1238 ms 24860 KB Output isn't correct
13 Incorrect 824 ms 32712 KB Output isn't correct