#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
struct node {
int x, prv, nxt;
node() : x(0), prv(0), nxt(0) {}
node(int x) : x(x), prv(0), nxt(0) {}
} ns[200001];
int tp = 0;
map<int, int> first;
map<int, int> group;
map<int, int> nodei;
void make_label(int x) {
if (nodei.count(x)) return;
int ni = ++tp;
ns[ni] = node(x);
nodei[x] = ni;
group[x] = x;
ns[first[x] = ++tp] = node();
ns[tp].nxt = ni;
ns[ni].prv = tp;
}
const int inf = 1e9;
bool T[50001];
int X[50001];
int ans[50001];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
make_label(a);
make_label(b);
int ai = nodei[a], bi = nodei[b];
if (ns[ai].prv) ns[ns[ai].prv].nxt = ns[ai].nxt;
if (ns[ai].nxt) ns[ns[ai].nxt].prv = ns[ai].prv;
ns[ai].prv = ns[ai].nxt = 0;
ns[ai].nxt = bi;
ns[ai].prv = ns[bi].prv;
if (ns[bi].prv) ns[ns[bi].prv].nxt = ai;
ns[bi].prv = ai;
}
vector<pii> ord;
int pri = 0;
for (auto it : first) {
int i = it.first;
int x = it.second;
if (pri + 1 <= i - 1) ord.emplace_back(pri + 1, i - 1);
pri = i;
for (x = ns[x].nxt; x; x = ns[x].nxt)
ord.emplace_back(ns[x].x, ns[x].x);
}
if (pri + 1 <= inf) ord.emplace_back(pri + 1, inf);
int q;
cin >> q;
vector<int> ql;
set<pii> qp;
for (int i = 1; i <= q; ++i) {
char in[10];
cin >> in >> X[i];
T[i] = in[0] == 'L';
if (T[i]) ql.push_back(i);
else qp.emplace(X[i], i);
}
sort(ql.begin(), ql.end(), [&](int a, int b) {
return X[a] < X[b];
});
int sum = 0, j = 0;
for (int i : ql) {
while (j < ord.size() && sum + ord[j].second - ord[j].first + 1 < X[i]) {
sum += ord[j].second - ord[j].first + 1;
++j;
}
ans[i] = X[i] - sum + ord[j].first - 1;
}
sum = 0;
for (pii i : ord) {
while (1) {
auto it = qp.lower_bound(pii(i.first, 0));
if (it == qp.end() || i.second < it->first)
break;
ans[it->second] = sum + it->first - i.first + 1;
qp.erase(it);
}
sum += i.second - i.first + 1;
}
for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message
queue.cpp: In function 'int main()':
queue.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < ord.size() && sum + ord[j].second - ord[j].first + 1 < X[i]) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
36 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
52 ms |
6776 KB |
Output is correct |
| 7 |
Correct |
51 ms |
6260 KB |
Output is correct |
| 8 |
Correct |
55 ms |
6768 KB |
Output is correct |
| 9 |
Correct |
68 ms |
7668 KB |
Output is correct |
| 10 |
Correct |
73 ms |
7924 KB |
Output is correct |
| 11 |
Correct |
139 ms |
9936 KB |
Output is correct |
| 12 |
Correct |
141 ms |
10020 KB |
Output is correct |
| 13 |
Correct |
142 ms |
9964 KB |
Output is correct |
| 14 |
Correct |
147 ms |
10016 KB |
Output is correct |
| 15 |
Correct |
155 ms |
10008 KB |
Output is correct |
| 16 |
Correct |
143 ms |
10476 KB |
Output is correct |
| 17 |
Correct |
22 ms |
3324 KB |
Output is correct |
| 18 |
Correct |
34 ms |
3784 KB |
Output is correct |
| 19 |
Correct |
55 ms |
4984 KB |
Output is correct |
| 20 |
Correct |
76 ms |
4940 KB |
Output is correct |
| 21 |
Correct |
120 ms |
10844 KB |
Output is correct |
| 22 |
Correct |
162 ms |
13032 KB |
Output is correct |
| 23 |
Correct |
212 ms |
15516 KB |
Output is correct |
| 24 |
Correct |
214 ms |
15620 KB |
Output is correct |
| 25 |
Correct |
258 ms |
14312 KB |
Output is correct |
