Submission #1010829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010829	2024-06-29T12:11:46 Z	vjudge1	Queue (CEOI06_queue)	C++17	50 / 100	274 ms	39712 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>> which;// 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<array<int, 3>> queries(q);
	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;
		}
		queries[i] = {y, x, i};
		if (x == 1){
			QQ++;
			which[y].push_back(i);
		}
	}
	vector<int> ans(q);
	int cur = (nxt.count(0) ? nxt[0] : 1);
	int pos = 1;
	while (QQ){
		debug(cur, pos);
		for (auto idx : which[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;
	}
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
queue.cpp:71:3: note: in expansion of macro 'debug'
   71 |   debug(cur, pos);
      |   ^~~~~

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	344 KB	Partially correct
2	Partially correct	0 ms	344 KB	Partially correct
3	Partially correct	1 ms	348 KB	Partially correct
4	Partially correct	2 ms	860 KB	Partially correct
5	Partially correct	99 ms	22592 KB	Partially correct
6	Partially correct	118 ms	24840 KB	Partially correct
7	Partially correct	50 ms	8272 KB	Partially correct
8	Partially correct	122 ms	26244 KB	Partially correct
9	Partially correct	119 ms	24148 KB	Partially correct
10	Partially correct	128 ms	24660 KB	Partially correct
11	Partially correct	122 ms	17744 KB	Partially correct
12	Partially correct	123 ms	12912 KB	Partially correct
13	Partially correct	162 ms	18640 KB	Partially correct
14	Partially correct	157 ms	20316 KB	Partially correct
15	Partially correct	146 ms	20648 KB	Partially correct
16	Partially correct	150 ms	19344 KB	Partially correct
17	Partially correct	25 ms	4444 KB	Partially correct
18	Partially correct	47 ms	8272 KB	Partially correct
19	Partially correct	67 ms	6228 KB	Partially correct
20	Partially correct	128 ms	15444 KB	Partially correct
21	Partially correct	166 ms	28968 KB	Partially correct
22	Partially correct	189 ms	30800 KB	Partially correct
23	Partially correct	267 ms	39004 KB	Partially correct
24	Partially correct	274 ms	39712 KB	Partially correct
25	Partially correct	212 ms	20584 KB	Partially correct