#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 2e5+5;
int n, mx[(1 << 20)], a[N];
struct node {
int ls, ans;
};
vector<node> t((1 << 19));
multiset<int, greater<>> val[N+N];
void mxupd(int l, int r, int x, int i, int v) {
if (l == r) {
mx[x] = v;
return;
}
int m = (l + r) >> 1;
if (i <= m)mxupd(l, m, x*2+1, i, v);
else mxupd(m+1, r, x*2+2, i, v);
mx[x] = max(mx[x*2+1], mx[x*2+2]);
}
int mxget(int li, int ri, int x, int l, int r) {
if (li > r || ri < l)return 0;
if (li >= l && ri <= r)return mx[x];
int m = (li + ri) >> 1;
return max(mxget(li, m, x*2+1, l, r), mxget(m+1, ri, x*2+2, l, r));
}
node nd;
node merge(node x, node y, int ly) {
return {
(y.ls == ly && a[x.ls] >= ly ? x.ls : y.ls),
x.ans + y.ans - (y.ls == ly && a[x.ls] >= ly ? 1 : 0)
};
}
void build(int li, int ri, int x) {
if (li == ri) {
t[x].ans = 1;
t[x].ls = li;
return;
}
int m = (li + ri) >> 1;
build(li, m, x*2+1);
build(m+1, ri, x*2+2);
t[x] = merge(t[x*2+1], t[x*2+2], m+1);
}
void get(int li, int ri, int x, int l, int r) {
if (li > r || ri < l)return;
if (li >= l && ri <= r) {
nd = merge(nd, t[x], li);
return;
}
int m = (li + ri) >> 1;
get(li, m, x*2+1, l, r);
get(m+1, ri, x*2+2, l, r);
}
int l[N], r[N];
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
set<int> st;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
val[i].insert(0);
val[n+i].insert(0);
st.insert(l[i]), st.insert(r[i]);
}
int cur = 1;
map<int, int> mp;
for (auto &x : st) {
mp[x] = cur++;
}
for (int i = 1; i <= n; i++) {
l[i] = mp[l[i]], r[i] = mp[r[i]];
}
int cr = n;
a[n] = n;
val[l[n]].insert(r[n]);
mxupd(1, 2*n, 0, l[n], r[n]);
for (int cl = n-1; cl >= 1; cl--) {
while (mxget(1, 2*n, 0, 1, r[cl]) >= l[cl]) {
val[l[cr]].erase(val[l[cr]].find(r[cr]));
mxupd(1, 2*n, 0, l[cr], *val[l[cr]].begin());
cr--;
}
val[l[cl]].insert(r[cl]);
mxupd(1, 2*n, 0, l[cl], *val[l[cl]].begin());
a[cl] = cr;
}
build(1, n, 0);
a[n+1] = -1;
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
nd.ans = 0;
nd.ls = n+1;
get(1, n, 0, a, b);
cout << nd.ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
711 ms |
83720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
783 ms |
86152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
711 ms |
83720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
