Submission #948151

#TimeUsernameProblemLanguageResultExecution timeMemory
948151blackavarOsumnjičeni (COCI21_osumnjiceni)C++14
110 / 110
283 ms51796 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...