Submission #659795

#	Time	Username	Problem	Language	Result	Execution time	Memory
659795		tibinyte	Osumnjičeni (COCI21_osumnjiceni)	C++17	60 / 110	1073 ms	62220 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxlog = 18;

struct aint
{
    vector<int> a;
    vector<int> lazy;
    void resize(int n)
    {
        a = lazy = vector<int>(4 * n);
    }
    void prop(int node, int left, int right)
    {
        a[node] += lazy[node];
        if (left != right)
        {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void update(int node, int left, int right, int st, int dr, int val)
    {
        prop(node, left, right);
        if (right < st || left > dr)
        {
            return;
        }
        if (st <= left && dr >= right)
        {
            lazy[node] += val;
            prop(node, left, right);
            return;
        }
        int mid = (left + right) / 2;
        update(2 * node, left, mid, st, dr, val);
        update(2 * node + 1, mid + 1, right, st, dr, val);
        a[node] = a[2 * node] + a[2 * node + 1];
    }
    int query(int node, int left, int right, int st, int dr)
    {
        prop(node, left, right);
        if (right < st || left > dr)
        {
            return 0;
        }
        if (st <= left && dr >= right)
        {
            return a[node];
        }
        int mid = (left + right) / 2;
        return query(2 * node, left, mid, st, dr) + query(2 * node + 1, mid + 1, right, st, dr);
    }
};
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n + 1);
    vector<int> norm;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].first >> a[i].second;
        norm.push_back(a[i].first);
        norm.push_back(a[i].second);
    }
    sort(norm.begin(), norm.end());
    map<int, int> qui;
    int p = 0;
    for (auto i : norm)
    {
        if (qui.find(i) == qui.end())
        {
            qui[i] = ++p;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        a[i].first = qui[a[i].first];
        a[i].second = qui[a[i].second];
    }
    aint tree;
    tree.resize(p);
    vector<int> next(n + 2);
    next[n + 1] = n + 1;
    int p2 = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (i != 1)
        {
            tree.update(1, 1, p, a[i - 1].first, a[i - 1].second, -1);
        }
        while (p2 <= n && tree.query(1, 1, p, a[p2].first, a[p2].second) == 0)
        {
            tree.update(1, 1, p, a[p2].first, a[p2].second, 1);
            p2++;
        }
        next[i] = p2;
    }
    vector<vector<int>> jump(n + 2, vector<int>(maxlog + 1));
    for (int i = 1; i <= n + 1; ++i)
    {
        jump[i][0] = next[i];
    }
    for (int j = 1; j <= maxlog; ++j)
    {
        for (int i = 1; i <= n + 1; ++i)
        {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int st, dr;
        cin >> st >> dr;
        int ans = 0;
        int wh = st;
        for (int i = maxlog; i >= 0; --i)
        {
            if (jump[wh][i] <= dr)
            {
                wh = jump[wh][i];
                ans += (1 << i);
            }
        }
        cout << ans + 1 << '\n';
    }
}

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