oj.uz

Submission #546041

# Submission time Handle Problem Language Result Execution time Memory
546041 2022-04-06T07:05:53 Z blue Cake (CEOI14_cake) C++17
0 / 100
 1259 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;
		}

		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;

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

			if(a <= b)
			{
				int rmx = S.rangemax(1, a, b);
				int prvp = S.locateprevgeq(a, 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, 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 683 ms 14084 KB Output isn't correct
2 Incorrect 312 ms 1836 KB Output isn't correct
3 Incorrect 406 ms 6284 KB Output isn't correct
4 Correct 175 ms 1304 KB Output is correct
5 Incorrect 709 ms 15156 KB Output isn't correct
6 Incorrect 571 ms 13260 KB Output isn't correct
7 Incorrect 444 ms 7536 KB Output isn't correct
8 Correct 233 ms 2772 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 10784 KB Output isn't correct
2 Incorrect 95 ms 10596 KB Output isn't correct
3 Incorrect 85 ms 10488 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 221 ms 25444 KB Output isn't correct
6 Incorrect 212 ms 25520 KB Output isn't correct
7 Incorrect 111 ms 25088 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 1356 KB Output isn't correct
2 Incorrect 40 ms 1116 KB Output isn't correct
3 Incorrect 93 ms 5548 KB Output isn't correct
4 Incorrect 134 ms 5680 KB Output isn't correct
5 Incorrect 174 ms 2988 KB Output isn't correct
6 Incorrect 186 ms 7420 KB Output isn't correct
7 Incorrect 168 ms 2784 KB Output isn't correct
8 Incorrect 256 ms 11800 KB Output isn't correct
9 Incorrect 1259 ms 29124 KB Output isn't correct
10 Incorrect 596 ms 9188 KB Output isn't correct
11 Incorrect 781 ms 10332 KB Output isn't correct
12 Incorrect 1215 ms 24664 KB Output isn't correct
13 Incorrect 831 ms 32620 KB Output isn't correct