Submission #1010835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010835	2024-06-29T12:18:34 Z	vjudge1	Queue (CEOI06_queue)	C++17	70 / 100	350 ms	38604 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; cin >> t;
		int x, y;
		x = t == 'P';
		cin >> y; 
		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);
	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

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	348 KB	Partially correct
2	Partially correct	0 ms	348 KB	Partially correct
3	Partially correct	1 ms	348 KB	Partially correct
4	Correct	3 ms	860 KB	Output is correct
5	Partially correct	103 ms	21928 KB	Partially correct
6	Correct	119 ms	23728 KB	Output is correct
7	Partially correct	57 ms	7632 KB	Partially correct
8	Partially correct	129 ms	25808 KB	Partially correct
9	Correct	132 ms	23232 KB	Output is correct
10	Partially correct	136 ms	23500 KB	Partially correct
11	Partially correct	143 ms	16976 KB	Partially correct
12	Correct	131 ms	12404 KB	Output is correct
13	Correct	163 ms	17744 KB	Output is correct
14	Correct	163 ms	19492 KB	Output is correct
15	Partially correct	177 ms	19792 KB	Partially correct
16	Correct	158 ms	18288 KB	Output is correct
17	Partially correct	27 ms	4052 KB	Partially correct
18	Partially correct	73 ms	7896 KB	Partially correct
19	Partially correct	73 ms	5476 KB	Partially correct
20	Partially correct	134 ms	14560 KB	Partially correct
21	Partially correct	191 ms	28532 KB	Partially correct
22	Correct	209 ms	29900 KB	Output is correct
23	Correct	340 ms	37456 KB	Output is correct
24	Correct	350 ms	38604 KB	Output is correct
25	Partially correct	223 ms	19820 KB	Partially correct