Submission #1010838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010838	2024-06-29T12:22:52 Z	vjudge1	Queue (CEOI06_queue)	C++17	100 / 100	306 ms	38440 KB

queue

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
//#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
map<int, int> prv, nxt;
map<int, vector<int>> type_p;// which position is i

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		int pa = (prv.count(a) ? prv[a] : a - 1);
		int na = (nxt.count(a) ? nxt[a] : a + 1);
		nxt[pa] = na;
		prv[na] = pa;

		int pb = (prv.count(b) ? prv[b] : b - 1);
		nxt[pb] = a;
		prv[a] = pb;
		nxt[a] = b;
		prv[b] = a;
	}
	int q;
	cin >> q;
	vector<pii> type_l;
	int QQ = 0;
	for (int i = 0; i <= q; i++){
		char t; 
		int x, y;
		if (i < q) cin >> t >> y;
		else {
			t = 'P';
			y = 1e9;
		}
		x = t == 'P';
		if (nxt.count(y) == 0){
			nxt[y] = y + 1;
			prv[y + 1] = y;
		}
		if (prv.count(y) == 0){
			prv[y] = y - 1;
			nxt[y - 1] = y;
		}
		if (x == 1){
			QQ++;
			type_p[y].push_back(i);
		}
		else {
			type_l.push_back({y, i});
		}
	}
	sort(all(type_l));
	vector<int> ans(q + 1);
	int cur = (nxt.count(0) ? nxt[0] : 1);
	int pos = 1;
	int ptr = 0;
	while (QQ){
		while (ptr < sz(type_l) && type_l[ptr].F <= pos){
			ans[type_l[ptr].S] = cur - (pos - type_l[ptr].F);
			ptr++;
		}
		for (auto idx : type_p[cur]) ans[idx] = pos, QQ--;
		if (nxt.count(cur)){
			cur = nxt[cur];
			pos++;
		} else {
			int up = nxt.upper_bound(cur)->first;
			pos += up - cur;
			cur = up;
		}
	}
	for (int i = 0; i < q; i++){
		cout << ans[i] << endl;
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	3 ms	916 KB	Output is correct
5	Correct	103 ms	22068 KB	Output is correct
6	Correct	115 ms	23836 KB	Output is correct
7	Correct	59 ms	7628 KB	Output is correct
8	Correct	125 ms	25800 KB	Output is correct
9	Correct	126 ms	23244 KB	Output is correct
10	Correct	133 ms	23756 KB	Output is correct
11	Correct	160 ms	16976 KB	Output is correct
12	Correct	124 ms	12588 KB	Output is correct
13	Correct	148 ms	17748 KB	Output is correct
14	Correct	154 ms	19536 KB	Output is correct
15	Correct	159 ms	19916 KB	Output is correct
16	Correct	152 ms	18512 KB	Output is correct
17	Correct	36 ms	4560 KB	Output is correct
18	Correct	56 ms	8020 KB	Output is correct
19	Correct	70 ms	5308 KB	Output is correct
20	Correct	147 ms	14792 KB	Output is correct
21	Correct	169 ms	28228 KB	Output is correct
22	Correct	213 ms	29760 KB	Output is correct
23	Correct	290 ms	37460 KB	Output is correct
24	Correct	306 ms	38440 KB	Output is correct
25	Correct	177 ms	19400 KB	Output is correct