This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct doan{
long long l, r;
};
long long n;
doan arr[1000005];
set <pair<long long, long long>> pi;
long long st[200005][18];
bool canInsert(long long pos) {
if (pi.empty()) return true;
auto it = pi.lower_bound({arr[pos].l, 1e18});
int nxt = it -> second;
if (arr[pos].l <= arr[nxt].l && arr[nxt].l <= arr[pos].r) return false;
if (it != pi.begin()) {
it--;
int prv = it -> second;
if (arr[prv].l <= arr[pos].l && arr[pos].l <= arr[prv].r) return false;
}
return true;
}
void preprocess() {
long long lim = 0;
for (int i = 1; i <= n; i++) {
if (lim < i) {
pi.clear();
lim = i;
pi.insert({arr[i].l, i});
}
while (lim + 1 <= n && canInsert(lim + 1)) {
lim++;
pi.insert({arr[lim].l, lim});
}
st[i][0] = lim + 1;
pi.erase({arr[i].l, i});
}
st[n + 1][0] = n + 1;
for (int i = 1; i < 18; i++) {
for (int j = 1; j <= n + 1; j++) {
st[j][i] = st[st[j][i - 1]][i - 1];
}
}
}
long long get(long long l, long long r) {
long long res = 1;
for (int i = 17; i >= 0; i--) {
if (st[l][i] <= r) {
l = st[l][i];
res += 1 << i;
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i].l >> arr[i].r;
}
long long t;
cin >> t;
preprocess();
while (t--) {
long long p, q;
cin >> p >> q;
cout << get(p, q) << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |