| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136281 |
2019-07-25T05:35:20 Z |
송준혁(#3262) |
Queue (CEOI06_queue) |
C++14 |
|
213 ms |
8540 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int N, Q;
struct Block{
int L, R, pos;
int pre, nxt;
} B[202020];
int num=3;
map<int, int> M;
int S[202020], C[202020];
int main(){
scanf("%d", &N);
B[0].nxt = 1;
B[1].L = 1, B[1].R = 1000000000, B[1].nxt = 2;
B[2].L = B[2].R = 1000000001, B[2].pre = 1;
M[1000000000] = 1;
while (N--){
int x, y;
scanf("%d %d", &x, &y);
int k = M.lower_bound(x)->second;
if (x != B[k].R){
B[num].L = B[k].L, B[num].R = x;
B[num].pre = B[k].pre, B[num].nxt = k;
B[k].L = x+1, B[k].pre = num;
B[B[num].pre].nxt = num;
M[x] = num, k = num++;
}
if (x != B[k].L){
B[num].L = x, B[num].R = B[k].R;
B[num].pre = k, B[num].nxt = B[k].nxt;
B[k].R = x-1, B[k].nxt = num;
B[B[num].nxt].pre = num;
M[B[num].R] = num, M[B[k].R] = k, k = num++;
}
int p = M.lower_bound(y)->second;
if (y != B[p].L){
B[num].L = y, B[num].R = B[p].R;
B[num].pre = p, B[num].nxt = B[p].nxt;
B[p].R = y-1, B[p].nxt = num;
B[B[num].nxt].pre = num;
M[B[num].R] = num, M[B[p].R] = p, p = num++;
}
B[B[k].pre].nxt = B[k].nxt;
B[B[k].nxt].pre = B[k].pre;
B[k].pre = B[p].pre, B[k].nxt = p;
B[B[p].pre].nxt = k, B[p].pre = k;
}
int p=0;
num=0;
while (p != 2){
B[p].pos = num;
S[num] = B[p].L;
C[num++] = B[p].R - B[p].L + 1;
p = B[p].nxt;
}
C[0] = 0;
for (int i=1; i<num; i++) C[i] += C[i-1];
scanf("%d", &Q);
while (Q--){
char ch;
int x;
scanf(" %c %d", &ch, &x);
if (ch == 'P'){
int k = M.lower_bound(x)->second;
printf("%d\n", C[B[k].pos-1] + (x - B[k].L + 1));
}
else{
int k = lower_bound(C+1, C+num, x)-C;
printf("%d\n", S[k]+x-C[k-1]-1);
}
}
return 0;
}
Compilation message
queue.cpp: In function 'int main()':
queue.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
queue.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
queue.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
queue.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %d", &ch, &x);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
27 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
37 ms |
1412 KB |
Output is correct |
| 7 |
Correct |
40 ms |
1912 KB |
Output is correct |
| 8 |
Correct |
47 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
54 ms |
2936 KB |
Output is correct |
| 10 |
Correct |
60 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
96 ms |
5880 KB |
Output is correct |
| 12 |
Correct |
82 ms |
4856 KB |
Output is correct |
| 13 |
Correct |
105 ms |
6012 KB |
Output is correct |
| 14 |
Correct |
104 ms |
5980 KB |
Output is correct |
| 15 |
Correct |
105 ms |
5980 KB |
Output is correct |
| 16 |
Correct |
111 ms |
6008 KB |
Output is correct |
| 17 |
Correct |
19 ms |
516 KB |
Output is correct |
| 18 |
Correct |
30 ms |
888 KB |
Output is correct |
| 19 |
Correct |
50 ms |
1144 KB |
Output is correct |
| 20 |
Correct |
69 ms |
1528 KB |
Output is correct |
| 21 |
Correct |
88 ms |
5944 KB |
Output is correct |
| 22 |
Correct |
140 ms |
7120 KB |
Output is correct |
| 23 |
Correct |
213 ms |
8540 KB |
Output is correct |
| 24 |
Correct |
159 ms |
8440 KB |
Output is correct |
| 25 |
Correct |
141 ms |
6772 KB |
Output is correct |
