제출 #1212911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212911		BigBadBully	Event Hopping (BOI22_events)	C++20	40 / 100	1167 ms	589824 KiB

events

#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using ll = long long;
using namespace std;
const ll mod = 998244353;
// const int inf = 1e18;
const int maxn = 1 << 21;

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<pii> segs(n);
    for (auto &x : segs)
        cin >> x.ff >> x.ss;
    vector<int> cs;
    for (auto x : segs)
        cs.push_back(x.ff), cs.push_back(x.ss);
    sort(cs.begin(), cs.end());
    cs.resize(unique(cs.begin(), cs.end()) - cs.begin());
    for (auto &x : segs)
        x.ff = lower_bound(cs.begin(), cs.end(), x.ff) - cs.begin(),
        x.ss = lower_bound(cs.begin(), cs.end(), x.ss) - cs.begin();
    int k = cs.size();
    vector<vector<int>> add(k);
    for (auto &x : segs)
        add[x.ff].push_back(x.ss);
    for (auto &v : add)
        if (v.size())
            sort(v.begin(), v.end());
    if (q > 100)
    {
        vector<vector<int>> prec(n);
        for (int b = 0; b < n; b++)
        {
            int e = segs[b].ss;
            vector<int> jmp(e + 2, -1);
            int total = -1;
            for (int i = 0; i < e; i++)
            {
                for (int x : add[i])
                {
                    if (x <= e)
                        total = max(total, x);
                    if (i == segs[b].ff)
                        total = e + 1;
                }
                if (total >= i)
                    jmp[i] = total;
            }
            vector<int> dp(e + 2, -1);
            dp[e + 1] = 0;
            dp[e] = 1;
            for (int i = e - 1; i >= 0; i--)
                if (jmp[i] >= 0 && dp[jmp[i]] >= 0)
                    dp[i] = 1 + dp[jmp[i]];
            prec[b] = dp;   
        }
        while(q--)
        {
            int a,b;
            cin >> a >> b;
            if (segs[--a].ss > segs[--b].ss)
            {
                cout << "impossible\n";
                continue;
            }
            if (a==b)
            {
                cout << "0\n";continue;
            }
            if (prec[b][segs[a].ss] < 0)
                cout << "impossible\n";
            else
                cout << prec[b][segs[a].ss] << '\n';
        }
        return;
    }
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        if (a == b)
        {
            cout << "0\n";
            continue;
        }
        if (segs[--a].ss > segs[--b].ss)
        {
            cout << "impossible\n";
            continue;
        }
        int e = segs[b].ss;
        vector<int> jmp(e + 2, -1);
        int total = -1;
        for (int i = 0; i < e; i++)
        {
            for (int x : add[i])
            {
                if (x <= e)
                    total = max(total, x);
                if (i == segs[b].ff)
                    total = e + 1;
            }
            if (total >= i)
                jmp[i] = total;
        }
        vector<int> dp(e + 2, -1);
        dp[e + 1] = 0;
        dp[e] = 1;
        for (int i = e - 1; i >= 0; i--)
            if (jmp[i] >= 0 && dp[jmp[i]] >= 0)
                dp[i] = 1 + dp[jmp[i]];
        if (dp[segs[a].ss] < 0)
            cout << "impossible\n";
        else
            cout << dp[segs[a].ss] << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    srand(time(0));

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30