답안 #546084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546084 2022-04-06T09:56:30 Z blue 케이크 (CEOI14_cake) C++17
0 / 100
1434 ms 33040 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)
	{
		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 = max(S.rangemax(1, a+1, b), d[a-1]-1);
				// 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+1);
				// cerr << "prvp = " << prvp << '\n';

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

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

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

	// cerr << "exit cake\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 788 ms 14184 KB Output isn't correct
2 Correct 324 ms 2232 KB Output is correct
3 Correct 469 ms 6524 KB Output is correct
4 Correct 191 ms 1688 KB Output is correct
5 Incorrect 779 ms 15716 KB Output isn't correct
6 Incorrect 607 ms 13648 KB Output isn't correct
7 Correct 510 ms 7944 KB Output is correct
8 Correct 249 ms 3156 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 11128 KB Output is correct
2 Incorrect 84 ms 10920 KB Output isn't correct
3 Correct 74 ms 10964 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 250 ms 25756 KB Output is correct
6 Incorrect 211 ms 25748 KB Output isn't correct
7 Correct 121 ms 25576 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 1740 KB Output isn't correct
2 Correct 55 ms 1464 KB Output is correct
3 Correct 100 ms 5892 KB Output is correct
4 Incorrect 156 ms 6192 KB Output isn't correct
5 Incorrect 187 ms 3296 KB Output isn't correct
6 Correct 199 ms 7884 KB Output is correct
7 Correct 173 ms 3208 KB Output is correct
8 Correct 261 ms 12184 KB Output is correct
9 Incorrect 1434 ms 29436 KB Output isn't correct
10 Incorrect 637 ms 9336 KB Output isn't correct
11 Incorrect 818 ms 10640 KB Output isn't correct
12 Correct 1309 ms 25016 KB Output is correct
13 Incorrect 908 ms 33040 KB Output isn't correct