답안 #546085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546085 2022-04-06T10:01:13 Z blue 케이크 (CEOI14_cake) C++17
0 / 100
1321 ms 32580 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) //find the largest i <= p such that S[i] >= 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) 
			{
				cerr << "??????\n";
				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);

	// cerr << "enter cake\n";

	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 = 0; i <= N+1; i++) cerr << S.rangemax(1, i, i) << ' ';
	// 			cerr << '\n';

	for(int j = 1; j <= Q; j++)
	{
		char c;
		cin >> c;

		if(c == 'E')
		{
			// cerr << "enter E\n";
			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 = 0; i <= N+1; i++) cerr << S.rangemax(1, i, i) << ' ';
			// 	cerr << '\n';

			// cerr << "exit E\n";
		}
		else
		{
			// cerr << "enter F\n";

			int b;
			cin >> b;

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

			if(a < b)
			{
				// cerr << "hello " << a << ' ' << b << " \n";
				int rmx = S.rangemax(1, a+1, b);
				// cerr << "rmx = " << rmx << '\n';
				// cerr << "a-1 = " << a-1 << '\n';
				// cerr << "locate prev geq " << a-1 << ' ' << rmx+1 << '\n';
				int prvp = S.locateprevgeq(a-1, rmx);
				// cerr << "prvp = " << prvp << '\n';

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

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

			// cerr << "exit F\n";
		}
	}

	// cerr << "exit cake\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 702 ms 13952 KB Output isn't correct
2 Correct 350 ms 1792 KB Output is correct
3 Correct 408 ms 6244 KB Output is correct
4 Correct 207 ms 1236 KB Output is correct
5 Incorrect 700 ms 15184 KB Output isn't correct
6 Incorrect 660 ms 13492 KB Output isn't correct
7 Correct 503 ms 7588 KB Output is correct
8 Correct 238 ms 2760 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 10628 KB Output is correct
2 Incorrect 87 ms 10568 KB Output isn't correct
3 Correct 77 ms 10420 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 212 ms 25436 KB Output is correct
6 Incorrect 227 ms 25392 KB Output isn't correct
7 Correct 144 ms 25228 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 1292 KB Output isn't correct
2 Correct 40 ms 1100 KB Output is correct
3 Correct 109 ms 5552 KB Output is correct
4 Incorrect 131 ms 5648 KB Output isn't correct
5 Incorrect 184 ms 2964 KB Output isn't correct
6 Correct 183 ms 7508 KB Output is correct
7 Correct 180 ms 2784 KB Output is correct
8 Correct 270 ms 11864 KB Output is correct
9 Incorrect 1321 ms 29160 KB Output isn't correct
10 Incorrect 668 ms 8916 KB Output isn't correct
11 Incorrect 862 ms 10348 KB Output isn't correct
12 Correct 1274 ms 24692 KB Output is correct
13 Incorrect 874 ms 32580 KB Output isn't correct