Submission #659809

#	Time	Username	Problem	Language	Result	Execution time	Memory
659809		tibinyte	Osumnjičeni (COCI21_osumnjiceni)	C++14	0 / 110	469 ms	39372 KiB

Main

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

const int maxlog = 18;

struct bit
{
    vector<int> b;
    void resize(int n)
    {
        b.resize(n + 2);
    }
    void update(int pos, int val)
    {
        int n = (int)b.size() - 1;
        for (int i = pos; i <= n; i += i & (-i))
        {
            b[i] += val;
        }
    }
    void update(int st, int dr, int val)
    {
        update(st, val);
        update(dr + 1, -val);
    }
    int query(int pos)
    {
        int ans = 0;
        for (int i = pos; i; i -= i & (-i))
        {
            ans += b[i];
        }
        return ans;
    }
};
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];
    }
    bit 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(a[i - 1].first, a[i - 1].second, -1);
        }
        while (p2 <= n && (tree.query(a[p2].first) == 0 && tree.query(a[p2].second) == 0))
        {
            tree.update(a[p2].first, a[p2].second, 1);
            p2++;
        }
        next[i] = p2;
    }
    int jump[maxlog + 1][n + 2];
    for (int i = 1; i <= n + 1; ++i)
    {
        jump[0][i] = next[i];
    }
    for (int j = 1; j <= maxlog; ++j)
    {
        for (int i = 1; i <= n + 1; ++i)
        {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
        }
    }
    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[i][wh] <= dr)
            {
                wh = jump[i][wh];
                ans += (1 << i);
            }
        }
        cout << ans + 1 << '\n';
    }
}

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