oj.uz

답안 #1010815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010815 2024-06-29T11:56:10 Z vjudge1 Queue (CEOI06_queue) C++17
4 / 100
 199 ms 19024 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;

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);
	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};
	}
	sort(all(queries));
	vector<int> ans(q);
	
	int cur = (nxt.count(0) ? nxt[0] : 1);
	int pos = 1;

	for (int i = 0; i < q; i++){
		while (pos < queries[i][0]){
			if (nxt.count(cur)){
				cur = nxt[cur];
				pos++;
			} else {
				int up = nxt.upper_bound(cur)->first;
				pos += up - cur;
				cur = up;
			}
		}
		debug(queries[i], cur, pos);
		ans[queries[i][2]] = cur;
	}
	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:78:3: note: in expansion of macro 'debug'
   78 |   debug(queries[i], cur, pos);
      |   ^~~~~

Subtask #1
4.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Partially correct 2 ms 344 KB Partially correct
4 Incorrect 4 ms 600 KB Output isn't correct
5 Incorrect 78 ms 11152 KB Output isn't correct
6 Incorrect 78 ms 11552 KB Output isn't correct
7 Incorrect 45 ms 5456 KB Output isn't correct
8 Incorrect 93 ms 13392 KB Output isn't correct
9 Incorrect 87 ms 11928 KB Output isn't correct
10 Incorrect 99 ms 12248 KB Output isn't correct
11 Incorrect 107 ms 8528 KB Output isn't correct
12 Incorrect 98 ms 6736 KB Output isn't correct
13 Incorrect 114 ms 9040 KB Output isn't correct
14 Incorrect 122 ms 9808 KB Output isn't correct
15 Incorrect 117 ms 10064 KB Output isn't correct
16 Incorrect 110 ms 9500 KB Output isn't correct
17 Incorrect 31 ms 3668 KB Output isn't correct
18 Incorrect 49 ms 5456 KB Output isn't correct
19 Incorrect 60 ms 4436 KB Output isn't correct
20 Incorrect 117 ms 9804 KB Output isn't correct
21 Incorrect 123 ms 13924 KB Output isn't correct
22 Incorrect 149 ms 15444 KB Output isn't correct
23 Incorrect 199 ms 18512 KB Output isn't correct
24 Incorrect 196 ms 19024 KB Output isn't correct
25 Incorrect 148 ms 12372 KB Output isn't correct