oj.uz

답안 #1010829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010829 2024-06-29T12:11:46 Z vjudge1 Queue (CEOI06_queue) C++17
50 / 100
 274 ms 39712 KB 
#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

# 결과 실행 시간 메모리 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