oj.uz

Submission #546040

# Submission time Handle Problem Language Result Execution time Memory
546040 2022-04-06T07:00:18 Z blue Cake (CEOI14_cake) C++17
0 / 100
 1010 ms 38904 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;

			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)
				elements.insert(x);
		}
		else
		{
			int b;
			cin >> b;

			if(a <= b)
			{
				int rmx = S.rangemax(1, a, b);
				int prvp = S.locateprevgeq(a, rmx);

				cout << b - prvp - 1 << '\n';
			}
			else
			{
				int rmx = S.rangemax(1, b, a);
				int nxtp = S.locatenextgeq(a, rmx);

				cout << nxtp - b - 1 << '\n';
			}
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 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 536 ms 18352 KB Output isn't correct
2 Incorrect 279 ms 6184 KB Output isn't correct
3 Incorrect 359 ms 10588 KB Output isn't correct
4 Incorrect 167 ms 5708 KB Output isn't correct
5 Incorrect 598 ms 19928 KB Output isn't correct
6 Incorrect 471 ms 18272 KB Output isn't correct
7 Incorrect 396 ms 12424 KB Output isn't correct
8 Incorrect 204 ms 7740 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 11944 KB Output isn't correct
2 Incorrect 103 ms 12008 KB Output isn't correct
3 Incorrect 81 ms 11852 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 237 ms 27908 KB Output isn't correct
6 Incorrect 219 ms 27768 KB Output isn't correct
7 Incorrect 122 ms 27332 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 1724 KB Output isn't correct
2 Incorrect 32 ms 1516 KB Output isn't correct
3 Incorrect 89 ms 6468 KB Output isn't correct
4 Incorrect 117 ms 6604 KB Output isn't correct
5 Incorrect 148 ms 4080 KB Output isn't correct
6 Incorrect 154 ms 9072 KB Output isn't correct
7 Incorrect 138 ms 4300 KB Output isn't correct
8 Incorrect 209 ms 14268 KB Output isn't correct
9 Incorrect 1010 ms 35232 KB Output isn't correct
10 Incorrect 518 ms 12436 KB Output isn't correct
11 Incorrect 585 ms 14348 KB Output isn't correct
12 Incorrect 946 ms 30420 KB Output isn't correct
13 Incorrect 680 ms 38904 KB Output isn't correct