#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node {
int number, id;
int prv, nxt;
}a[100010], b[100010];
struct loveccf {
int id; int number;
}tlhll[100010];
int tanLilyisHardWorking[100010];
bool cmp(loveccf smartkkksc03, loveccf smtcz) {
if (smartkkksc03.number != smtcz.number)
return smartkkksc03.number < smtcz.number;
return smartkkksc03.id < smtcz.number;
}
map<int, int> toid; signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].id >> a[i].number;
b[i].id = tanLilyisHardWorking[i] = a[i].id;
tlhll[i].id = toid[a[i].id] = i;
b[i].nxt = a[i].nxt = i + 1;
a[i].prv = b[i].prv = i - 1;
b[i].number = tlhll[i].number = a[i].number;
}
sort(tanLilyisHardWorking + 1, tanLilyisHardWorking + 1 + n);
b[1].prv = b[n].nxt = a[1].prv = a[n].nxt = -1;
sort(tlhll + 1, tlhll + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
int now = tlhll[i].id;
if (b[now].prv != -1) {
a[now].prv = b[now].prv;
} else {
a[now].prv = now;
}
if (b[now].nxt != -1) {
a[now].nxt = b[now].nxt;
if (b[now].prv != -1) {
b[b[now].prv].nxt = b[now].nxt;
}
b[b[now].nxt].prv = b[now].prv;
} else {
b[b[now].prv].nxt = b[now].nxt;
a[now].nxt = now;
}
}
int q, l, c;
cin >> q;
bool flag = 0;
while (q--) {
cin >> l >> c;
flag = 0;
cout << toid[l] << endl;
if (toid[l] == 0) {
int ll = 1, rr = n, mid;
while (ll < rr) {
mid = ll + rr + 1 >> 1;
if (tanLilyisHardWorking[mid] < l) {
ll = mid;
} else {
rr = mid + 1;
}
}
flag = 1;
l = ll;
} if (toid[c] == 0) {
int ll = 1, rr = n, mid;
while (ll < rr) {
mid = ll + rr + 1 >> 1;
if (tanLilyisHardWorking[mid] < c) {
ll = mid;
} else {
rr = mid + 1;
}
}
flag = 1;
c = ll;
}
if (c > l) {
if (a[toid[l]].nxt > toid[c] || a[toid[l]].nxt == toid[l]) {
if (toid[c] - toid[l] == c - l && !flag) {
cout << "true";
} else {
cout << "maybe";
}
} else {
cout << "false";
}
} else {
if (a[toid[l]].prv < toid[c] || a[toid[l]].prv == toid[l]) {
if (toid[c] - toid[l] == c - l && !flag) { cout << "true";
} else {
cout << "maybe";
}
} else {
cout << "false";
}
}
cout << endl;
}
return 0;
}
共 5 条回复
@shaobai ???
啥不行 @shaobai
@root
我们题库应该不行[doge]
https://www.luogu.com.cn/problem/P2471