#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const int inf = 1e9 + 10;
struct SegmentTree{
vector<int> tree;
void init(int n) {
int sz = 1 << __lg(n-1) + 2;
tree.assign(sz, -inf);
}
void update(int node, int s, int e, int tar, int val) {
if (s > tar || tar > e) return;
if (s == e) {
tree[node] = val;
return;
}
int mid = s + e >> 1;
update(node*2, s, mid, tar, val);
update(node*2+1, mid+1, e, tar, val);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
int Findleft(int node, int s, int e, int l, int r, int k) {
if (l > e || s > r || tree[node] < k) return -1;
if (s == e) return tree[node] >= k ? s : -1;
int mid = s + e >> 1;
int t = Findleft(node*2, s, mid, l, r, k);
if (t != -1) return t;
return Findleft(node*2+1, mid+1, e, l, r, k);
}
int Findright(int node, int s, int e, int l, int r, int k) {
if (l > e || s > r || tree[node] < k) return -1;
if (s == e) return tree[node] >= k ? s : -1;
int mid = s + e >> 1;
int t = Findright(node*2+1, mid+1, e, l, r, k);
if (t != -1) return t;
return Findright(node*2, s, mid, l, r, k);
}
};
int N, M;
int A[200010], B[200010];
int QA[200010], QB[200010];
SegmentTree seg1, rseg2;
SegmentTree segA, segB;
SegmentTree rsegA, rsegB;
vector<int> solve() {
vector<int> sA[N+M+1], sB[N+M+1], sQ[N+M+1];
for (int i=1; i<=N; i++) {
sA[A[i]].push_back(i);
sB[B[i]].push_back(i);
sQ[QB[i]].push_back(i);
}
vector<int> id(M);
iota(id.begin(), id.end(), 1);
sort(id.begin(), id.end(), [&] (int &u, int &v) {
return QB[u] < QB[v];
});
vector<int> ret(M+1, 0);
vector<int> prmxa(N+2, 0), prmxb(N+2, 0), prmna(N+2, 1e9), prmnb(N+2, 1e9);
vector<int> sumxa(N+2, 0), sumxb(N+2, 0), sumna(N+2, 1e9), sumnb(N+2, 1e9);
for (int i=1; i<=N; i++) {
prmxa[i] = max(prmxa[i-1], A[i]);
prmxb[i] = max(prmxb[i-1], B[i]);
prmna[i] = min(prmna[i-1], A[i]);
prmnb[i] = min(prmnb[i-1], B[i]);
}
for (int i=N; i>=1; i--) {
sumxa[i] = max(sumxa[i+1], A[i]);
sumxb[i] = max(sumxb[i+1], B[i]);
sumna[i] = min(sumna[i+1], A[i]);
sumnb[i] = min(sumnb[i+1], B[i]);
}
seg1.init(N); rseg2.init(N);
segA.init(N); segB.init(N);
rsegA.init(N); rsegB.init(N);
for (int i=1; i<=N; i++) {
segA.update(1, 1, N, i, A[i]);
segB.update(1, 1, N, i, B[i]);
rsegA.update(1, 1, N, i, -A[i]);
rsegB.update(1, 1, N, i, -B[i]);
rseg2.update(1, 1, N, i, -A[i]);
}
int p = 0;
for (int Bx=1; Bx<=N+M; Bx ++) {
for (auto &i : sB[Bx]) {
seg1.update(1, 1, N, i, A[i]);
}
for (auto &i : sQ[Bx]) {
if (sA[QA[i]].empty() || sB[QB[i]].empty()) continue;
int lm = sB[QB[i]][0], rm = sA[QA[i]].back();
if (lm > rm) continue;
if (lm == rm) {
if (lm != 1 && (prmxa[lm-1] < QA[i] || prmxb[lm-1] < QB[i]) && (prmna[lm-1] > QA[i] || prmnb[lm-1] > QB[i])) continue;
if (rm != N && (sumxa[rm+1] < QA[i] || sumxb[rm+1] < QB[i]) && (sumna[rm+1] > QA[i] || sumnb[rm+1] > QB[i])) continue;
ret[i] = 1;
continue;
}
//cout << i << ' ' << lm << ' ' << rm << '\n';
int lh = N+1;
if (A[1] <= QA[i] && B[1] >= QB[i]) {
lh = 1;
}
else {
int nonA = rsegA.Findleft(1, 1, N, 1, N, -QA[i]);
int nonB = segB.Findleft(1, 1, N, 1, N, QB[i]);
int non;
if (nonA == -1) non = nonB;
else if (nonB == -1) non = nonA;
else non = min(nonA, nonB);
lh = rseg2.Findleft(1, 1, N, non+1, N, -QA[i]);
}
if (lh == -1 || lh > sB[QB[i]].back()) lh = N+1;
else {
int idx = lower_bound(sB[QB[i]].begin(), sB[QB[i]].end(), lh) - sB[QB[i]].begin();
lh = sB[QB[i]][idx];
}
int rh = 0;
if (A[N] >= QA[i] && B[N] <= QB[i]) {
rh = N;
}
else {
int nonA = segA.Findright(1, 1, N, 1, N, QA[i]);
int nonB = rsegB.Findright(1, 1, N, 1, N, -QB[i]);
int non;
if (nonA == -1) non = nonB;
else if (nonB == -1) non = nonA;
else non = max(nonA, nonB);
rh = seg1.Findleft(1, 1, N, 1, non-1, QA[i]);
}
if (rh == -1 || rh < sA[QA[i]][0]) rh = 0;
else {
int idx = upper_bound(sA[QA[i]].begin(), sA[QA[i]].end(), rh) - sA[QA[i]].begin() - 1;
rh = sA[QA[i]][idx];
}
int le = rseg2.Findleft(1, 1, N, lm+1, N, -QA[i]);
if (le == -1) le = N+1;
int re = seg1.Findright(1, 1, N, 1, rm-1, QA[i]);
if (re == -1) re = 0;
if (min(max(lh, lm), le) < max(min(rh, rm), re)) {
ret[i] = 1;
}
}
for (auto &i : sB[Bx]) {
rseg2.update(1, 1, N, i, -inf);
}
}
return ret;
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
vector<int> ta, tb;
for (int i=1; i<=N; i++) {
cin >> A[i] >> B[i];
ta.push_back(A[i]);
tb.push_back(B[i]);
}
for (int i=1; i<=M; i++) {
cin >> QA[i] >> QB[i];
ta.push_back(QA[i]);
tb.push_back(QB[i]);
}
sort(ta.begin(), ta.end());
ta.erase(unique(ta.begin(), ta.end()), ta.end());
sort(tb.begin(), tb.end());
tb.erase(unique(tb.begin(), tb.end()), tb.end());
for (int i=1; i<=N; i++) {
A[i] = lower_bound(ta.begin(), ta.end(), A[i]) - ta.begin() + 1;
B[i] = lower_bound(tb.begin(), tb.end(), B[i]) - tb.begin() + 1;
}
for (int i=1; i<=M; i++) {
QA[i] = lower_bound(ta.begin(), ta.end(), QA[i]) - ta.begin() + 1;
QB[i] = lower_bound(tb.begin(), tb.end(), QB[i]) - tb.begin() + 1;
}
vector<int> ret[4];
ret[0] = solve();
reverse(A+1, A+N+1);
reverse(B+1, B+N+1);
ret[1] = solve();
for (int i=1; i<=N; i++) {
A[i] = ta.size() - A[i] + 1;
B[i] = tb.size() - B[i] + 1;
}
for (int i=1; i<=M; i++) {
QA[i] = ta.size() - QA[i] + 1;
QB[i] = tb.size() - QB[i] + 1;
}
ret[2] = solve();
reverse(A+1, A+N+1);
reverse(B+1, B+N+1);
ret[3] = solve();
for (int i=1; i<=M; i++) {
int flag = 0;
for (int j=0; j<4; j++) {
flag |= ret[j][i];
}
if (flag) cout << i << ' ';
}
}
Compilation message
Main.cpp: In member function 'void SegmentTree::init(int)':
Main.cpp:13:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
13 | int sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
Main.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'int SegmentTree::Findleft(int, int, int, int, int, int)':
Main.cpp:30:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'int SegmentTree::Findright(int, int, int, int, int, int)':
Main.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'std::vector<int> solve()':
Main.cpp:90:9: warning: unused variable 'p' [-Wunused-variable]
90 | int p = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
