| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 136393 |
2019-07-25T08:27:08 Z |
이온조(#3259) |
Queue (CEOI06_queue) |
C++14 |
|
184 ms |
4596 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 2e9;
vector<int> S, PR, NW, XS;
int A[50009], B[50009], L[100009], R[100009], P[100009], O[100009], M[100009];
bool chk(vector<int> &T, int x) { return x == *lower_bound(S.begin(), S.end(), x); }
int geti(vector<int> &T, int x) { return lower_bound(T.begin(), T.end(), x) - T.begin(); }
int getp(int x) { return x + geti(NW, x) - geti(PR, x); }
int getl(int x) { return x + geti(PR, x) - geti(XS, x); }
int getL(int x) {
int l = 1, r = 1e9, f = -1;
while(l <= r) {
int m = l+r >> 1;
int res = getp(m);
if(res <= x) l = m+1, f = m;
else r = m-1;
}
return f;
}
// void showpos() {
// printf("showing position\n");
// for(auto& it: P) printf("position of %d: %d\n", it.first, it.second);
// puts("\n\n");
// puts("relative order:");
// int now = R[0];
// while(now != INF) {
// printf("%d\n", now);
// now = R[now];
// }
// puts("\n\n");
// }
int main() {
int N; scanf("%d",&N);
for(int i=1; i<=N; i++) {
scanf("%d%d", &A[i], &B[i]);
S.push_back(A[i]);
S.push_back(B[i]);
}
S.push_back(0); S.push_back(INF);
sort(S.begin(), S.end()); S.resize(unique(S.begin(), S.end()) - S.begin());
int K = S.size() - 2;
R[0] = 1; L[K+1] = K;
for(int i=1; i<=K; i++) {
R[i] = i+1, L[i] = i-1, P[i] = i;
PR.push_back(S[i]);
}
PR.push_back(INF);
// showpos();
for(int i=1; i<=N; i++) {
int ai = geti(S, A[i]), bi = geti(S, B[i]);
int l = L[ai], r = R[ai];
R[l] = r; L[r] = l;
R[ai] = bi; L[ai] = L[bi];
R[L[bi]] = ai; L[bi] = ai;
P[ai] = P[bi];
// showpos();
}
int now = R[0], cnt = 1;
while(now != K+1) {
// printf("now: %d\n", now);
// printf("position: %d\n\n", P[now]);
NW.push_back(S[P[now]]);
if(!M[P[now]]) M[P[now]] = cnt;
O[now] = cnt;
// printf("position: %d\n\n", P[now]);
now = R[now];
++cnt;
}
vector<pii> X;
for(int i=1; i<=K; i++) {
P[i] = getp(S[P[i]]) + O[i] - M[P[i]];
X.push_back({P[i], S[i]});
XS.push_back(P[i]);
}
X.push_back({INF, INF});
XS.push_back(INF);
sort(X.begin(), X.end());
sort(XS.begin(), XS.end());
int Q; scanf("%d",&Q);
while(Q--) {
char t; int x; scanf(" %c%d",&t,&x);
if(t == 'P') {
if(chk(S, x)) printf("%d\n", P[geti(S, x)]);
else printf("%d\n", getp(x));
}
if(t == 'L') {
int a, b; tie(a, b) = *lower_bound(X.begin(), X.end(), (pii){x, -INF});
if(a == x) printf("%d\n", b);
else printf("%d\n", getL(x));
}
}
return 0;
}
Compilation message
queue.cpp: In function 'int getL(int)':
queue.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r >> 1;
~^~
queue.cpp: In function 'int main()':
queue.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d",&N);
~~~~~^~~~~~~~~
queue.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
queue.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int Q; scanf("%d",&Q);
~~~~~^~~~~~~~~
queue.cpp:90:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char t; int x; scanf(" %c%d",&t,&x);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
90 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
43 ms |
1228 KB |
Output is correct |
| 7 |
Correct |
93 ms |
1564 KB |
Output is correct |
| 8 |
Correct |
184 ms |
1836 KB |
Output is correct |
| 9 |
Correct |
123 ms |
1780 KB |
Output is correct |
| 10 |
Correct |
127 ms |
1916 KB |
Output is correct |
| 11 |
Correct |
68 ms |
3312 KB |
Output is correct |
| 12 |
Correct |
65 ms |
3440 KB |
Output is correct |
| 13 |
Correct |
71 ms |
3340 KB |
Output is correct |
| 14 |
Correct |
87 ms |
3384 KB |
Output is correct |
| 15 |
Correct |
90 ms |
3384 KB |
Output is correct |
| 16 |
Correct |
76 ms |
3432 KB |
Output is correct |
| 17 |
Correct |
37 ms |
1008 KB |
Output is correct |
| 18 |
Correct |
86 ms |
1140 KB |
Output is correct |
| 19 |
Correct |
80 ms |
1396 KB |
Output is correct |
| 20 |
Correct |
163 ms |
1904 KB |
Output is correct |
| 21 |
Correct |
146 ms |
3156 KB |
Output is correct |
| 22 |
Correct |
147 ms |
3952 KB |
Output is correct |
| 23 |
Correct |
154 ms |
4464 KB |
Output is correct |
| 24 |
Correct |
175 ms |
4596 KB |
Output is correct |
| 25 |
Correct |
153 ms |
4460 KB |
Output is correct |
