제출 #1280691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280691		Ludissey	Event Hopping (BOI22_events)	C++20	100 / 100	585 ms	128676 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<int>> mn(n,vector<int>(LOG,0));
    set<int> evs;
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second, evs.insert(a[i].first), evs.insert(a[i].second);
    unordered_map<int,int> um;
    int k=0;
    for (auto u : evs) um[u]=k++;
    vector<vector<pair<int,int>>> mn_table(k, vector<pair<int,int>>(LOG,{1e12,-1}));
    for (int i = 0; i < n; i++)
    {
        if(a[i].first< mn_table[um[a[i].second]][0].first) mn_table[um[a[i].second]][0]={a[i].first,i};
    }
    
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i+(1<<(j-1)) < k; i++)
        {
            if(mn_table[i][j-1].first<mn_table[i+(1<<(j-1))][j-1].first) mn_table[i][j]=mn_table[i][j-1];
            else mn_table[i][j]=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][0]=i;
        if(mn_table[l][lg].first<mn_table[r-(1<<lg)+1][lg].first) mn[i][0]=mn_table[l][lg].second;
        else if(mn_table[r-(1<<lg)+1][lg].first<1e12) mn[i][0]=mn_table[r-(1<<lg)+1][lg].second;
    }
    
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i < n; i++)
        {
            mn[i][j]=mn[mn[i][j-1]][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(a[mn[e][j]].first>a[s].second){
                sm+=(1<<j);
                e=mn[e][j];
            }
        }
        e=mn[e][0];
        if(a[e].first>a[s].second){ cout << "impossible\n"; continue; }
        sm+=2;
        cout << sm << "\n";
    }    
    return 0;
}

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