Submission #1212910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212910		BigBadBully	Event Hopping (BOI22_events)	C++20	25 / 100	1596 ms	11904 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());
    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: 0 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30