제출 #1282706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282706		stefanneagu	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	1099 ms	59836 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 2e5 + 1, l2 = 17, inf = 1e9 + 7;

struct str {
    int l, r;
} v[nmax];

int up[nmax][l2 + 1];
int n;

struct AINT {
    int aint[nmax * 4];
    int lz[nmax * 4];

    /*void lazy(int nod, int st, int dr) {
        if (st != dr) {
            aint[nod * 2] += lz[nod];
            lz[nod * 2] += lz[nod];
            aint[nod * 2 + 1] += lz[nod];
            lz[nod * 2 + 1] += lz[nod];
        }
        lz[nod] = 0;
    }

    void upd(int l, int r, int val, int nod = 1, int st = 1, int dr = n) {
        lazy(nod, st, dr);
        if (dr < l || r < st) {
            return;
        }
        if (l <= st && dr <= r) {
            lz[nod] += val;
            aint[nod] += val;
            lazy(nod, st, dr);
            return;
        }
        int mid = (st + dr) / 2;
        upd(l, r, val, nod * 2, st, mid);
        upd(l, r, val, nod * 2 + 1, mid + 1, dr);
        aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
    }

    int qry(int l, int r, int nod = 1, int st = 1, int dr = n) {
        lazy(nod, st, dr);
        if (dr < l || r < st) {
            return -inf;
        }
        if (l <= st && dr <= r) {
            return aint[nod];
        }
        int mid = (st + dr) / 2;
        return max(qry(l, r, nod * 2, st, mid), qry(l, r, nod * 2 + 1, mid + 1, dr));
    }*/

    void upd(int l, int r, int val) {
        for (int i = l; i <= r; i++) {
            aint[i] += val;
        }
        /*cout << "+" << val << " " << l << " " << r << '\n';
        for (int i = 1; i <= n; i++) {
            cout << aint[i] << ' ';
        }
        cout << '\n';*/
    }

    int qry(int l, int r) {
        int ans = -inf;
        for (int i = l; i <= r; i++) {
            ans = max(ans, aint[i]);
        }
        /*cout << "? " << l << " " << r << '\n';
        for (int i = 1; i <= n; i++) {
            cout << aint[i] << ' ';
        }
        cout << '\n';*/
        return ans;
    }
} ds;

void norm() {
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        mp[v[i].l], mp[v[i].r];
    }
    int cnt = 0;
    for (auto &[_, a] : mp) {
        a = ++cnt;
    }
    for (int i = 1; i <= n; i++) {
        v[i].l = mp[v[i].l];
        v[i].r = mp[v[i].r];
    }
}

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].l >> v[i].r;
        for (int bit = 0; bit <= l2; bit++) {
            up[i][bit] = inf;
        }
    }
    norm();
    for (int bit = 0; bit <= l2; bit++) {
        up[n + 1][bit] = inf;
    }
    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (j + 1 <= n && ds.qry(v[j + 1].l, v[j + 1].r) == 0) {
            j++;
            ds.upd(v[j].l, v[j].r, 1);
        }
        // cout << ds.qry()
        up[i][0] = j + 1;
        ds.upd(v[i].l, v[i].r, -1);
    }
    for (int bit = 1; bit <= l2; bit++) {
        for (int i = 1; i <= n; i++) {
            if (up[i][bit - 1] > nmax) {
                up[i][bit] = inf;
            } else {
                up[i][bit] = up[up[i][bit - 1]][bit - 1];
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int bit = l2; bit >= 0; bit--) {
            if (up[l][bit] <= r) {
                l = up[l][bit] + 1;
                ans += (1 << bit);
            }
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50