Submission #1278052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278052		Ludissey	Event Hopping (BOI22_events)	C++20	30 / 100	275 ms	115380 KiB

events

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

const int LOG=24;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,q; cin >> n >> q;
    vector<pair<int,int>> a(n);
    vector<vector<pair<int,int>>> lift(n+1,vector<pair<int,int>>(LOG,{-1,n}));
    vector<pair<pair<int,int>,int>> ev;
    vector<int> mn(n);
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second, ev.push_back({{a[i].first,0},i}), ev.push_back({{a[i].second,1},i});
    sort(all(ev));
    int mx=-1;
    int mxI=n;
    set<int> evs;
    unordered_map<int,int> um;
    for (int i = 0; i < sz(ev); i++)
    {
        evs.insert(ev[i].first.first);
        if(ev[i].first.second==0){
            if(a[ev[i].second].second>mx){
                mxI=ev[i].second;
                mx=a[ev[i].second].second;
            }
        }       
        else {
            lift[ev[i].second][0]={mx,mxI};
        }
    }
    int k=0;
    for (auto u : evs) um[u]=k++;
    vector<vector<int>> mn_table(k,vector<int>(LOG,1e12));
    for (int i = 0; i < n; i++)
    {
        mn_table[um[a[i].second]][0]=min(mn_table[um[a[i].second]][0],a[i].first);
    }
    
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i+(1<<(j-1)) < k; i++)
        {
            mn_table[i][j]=min(mn_table[i][j-1],mn_table[i+(1<<(j-1))][j-1]);
        }
        
    }
    for (int i = 0; i < n; i++)
    {
        int l=um[a[i].first],r=um[a[i].second];
        int lg=log2(r-l+1);
        mn[i]=min(mn_table[l][lg],mn_table[r-(1<<lg)+1][lg]);
    }
    
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i < n; i++)
        {
            lift[i][j]=lift[lift[i][j-1].second][j-1];
        }
    }
    vector<pair<int,int>> qrs(q);
    for (int i = 0; i < q; i++) cin >> qrs[i].first >> qrs[i].second;
    for (int i = 0; i < q; i++) {
        int s=qrs[i].first-1,e=qrs[i].second-1; 
        if(s==e){ cout << 0 << "\n"; continue; }
        if(a[s].second>a[e].second){ cout << "impossible\n"; continue; }
        else if(a[s].second>=a[e].first){ cout << 1 << "\n"; continue; }
        int sm=0;
        for (int j = LOG-1; j >= 0; j--)
        {
            if(lift[s][j].first<a[e].first){
                sm+=(1<<j);
                s=lift[s][j].second;
            }
        }
        if(mn[e]>a[s].second){ cout << "impossible\n"; continue; }
        sm+=2;
        cout << sm << "\n";
    }    
    return 0;
}

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