oj.uz

답안 #1010835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010835 2024-06-29T12:18:34 Z vjudge1 Queue (CEOI06_queue) C++17
70 / 100
 350 ms 38604 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>> 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

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