제출 #1266365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266365		canhnam357	Osumnjičeni (COCI21_osumnjiceni)	C++20	110 / 110	480 ms	35892 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int st[1 << 20]{}, lz[1 << 20]{};
void down(int id) {
    if (!lz[id]) return;
    for (int i : {id << 1, id << 1 | 1}) {
        st[i] += lz[id];
        lz[i] += lz[id];
    }
    lz[id] = 0;
}
void update(int u, int v, int x, int id, int l, int r) {
    if (r < u || l > v) return;
    if (l >= u && r <= v) {
        st[id] += x;
        lz[id] += x;
        return;
    }
    down(id);
    int mid = (l + r) >> 1;
    update(u, v, x, id << 1, l, mid);
    update(u, v, x, id << 1 | 1, mid + 1, r);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> cc;
    vector<pair<int, int>> a(n);
    for (auto &[l, r] : a) {
        cin >> l >> r;
        cc.push_back(l);
        cc.push_back(r);
    }   
    sort(cc.begin(), cc.end());
    cc.erase(unique(cc.begin(), cc.end()), cc.end());
    auto get_pos = [&](int pos) {
        return upper_bound(cc.begin(), cc.end(), pos) - cc.begin();
    };
    for (auto &[l, r] : a) {
        l = get_pos(l);
        r = get_pos(r);
    }
    int m = cc.size();
    vector<vector<int>> nxt(n, vector<int>(20, n));
    for (int l = n - 1, r = n - 1; l >= 0; l--) {
        update(a[l].first, a[l].second, 1, 1, 1, m);
        while (st[1] > 1) {
            update(a[r].first, a[r].second, -1, 1, 1, m);
            r--;
        }
        nxt[l][0] = r + 1;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (nxt[j][i - 1] < n) {
                nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int ans = 0;
        for (int i = 19; i >= 0; i--) {
            if (nxt[l][i] <= r) {
                ans += (1 << i);
                l = nxt[l][i];
            }
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}

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