Submission #523364

#	Time	Username	Problem	Language	Result	Execution time	Memory
523364		blue	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	417 ms	40496 KiB

Main

#include <iostream>
#include <vector>
#include <set>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;

const int lg = 18;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int l[1+n], r[1+n];
    for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];

    vvi nxt(1+n+1, vi(1+lg, 1+n));

    set<pii> S;

    int y = 0;
    for(int x = 1; x <= n; x++)
    {
        if(y < x)
        {
            y = x;
            S.insert({l[x], r[x]});
        }

        while(1)
        {
            bool bad = 0;

            pii z;

            if(y+1 > n) bad = 1;
            else
            {
                // cerr << "#\n";
                 z = {l[y+1], r[y+1]};

                auto it = S.lower_bound(z);
                if(it != S.end() && it->first <= r[y+1]) bad = 1;

                // cerr << "bad1 = " << bad << '\n';

                if(it != S.begin())
                {
                    it--;
                    // cerr << it->first << " " << it->second << " : " << l[x]
                    if(it->second >= l[y+1]) bad = 1;
                }
            }

            // cerr << x << ' ' << y+1 << ' ' << bad << '\n';
           

            if(bad)
            {
                nxt[x][0] = y+1;
                break;
            }
            else
            {
                y++;
                S.insert(z);
            }
        }

        S.erase({l[x], r[x]});
    }

    // for(int i = 1; i <= n; i++) cerr << nxt[i][0] << '\n';

    for(int e = 1; e <= lg; e++)
        for(int i = 1; i <= n; i++)
            nxt[i][e] = nxt[ nxt[i][e-1] ][e-1];

    int q;
    cin >> q;

    for(int j = 1; j <= q; j++)
    {
        int l, r;
        cin >> l >> r;
        r++;

        int res = 0;

        for(int e = lg; e >= 0; e--)
        {
            if(nxt[l][e] >= r) continue;
            // cerr << l << " -> " << nxt[l][e] << ' ' << (1<<e) << '\n';
            res += (1<<e);
            l = nxt[l][e];
        }

        res += 1;

        cout << res << '\n';
    }
}

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