제출 #1320063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320063		888313666	Event Hopping (BOI22_events)	C++20	0 / 100	65 ms	22832 KiB

events

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<endl

int n,m=0,q,k;
vector<int> x, s, e, idx;
vector<vector<int>> st, mn, qt;

int fmn(const int l, const int r) {
    const auto d=r-l;
    const auto lg=31-__builtin_clz(d);
    if ((1<<lg)==d) return mn[lg][l];
    if (st[lg][l]<st[lg][r-(1<<lg)]) return mn[lg][l];
    return mn[lg][r-(1<<lg)];
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>q;
    k=32-__builtin_clz(n);
    s.resize(n);
    e.resize(n);
    x.resize(n);
    for (int i=0; i<n; i++) {
        cin>>s[i]>>e[i];
    }
    iota(x.begin(), x.end(), 0);
    sort(x.begin(), x.end(), [](const int a, const int b){if (e[a]<e[b]) return true; if (e[a]>e[b]) return false; if (s[a]<s[b]) return true; return false;});
    idx.resize(n);
    for (int i=0; i<n; i++) idx[i]=e[x[i]];
    e=move(idx);
    idx.resize(n);
    for (int i=0; i<n; i++) idx[i]=s[x[i]];
    s=move(idx);
    idx.resize(n);
    for (int i=0; i<n; i++) idx[x[i]]=i;
    st.assign(k, vector<int>(n));
    mn.assign(k, vector<int>(n, -1));
    for (int i=0; i<n; i++) st[0][i]=s[i], mn[0][i]=i;
    for (int i=1; i<k; i++) for (int j=0; j+(1<<i-1)<n; j++) {
        if (st[i-1][j]<st[i-1][j+(1<<i-1)]) {
            st[i][j]=st[i-1][j];
            mn[i][j]=mn[i-1][j];
        } else {
            st[i][j]=st[i-1][j+(1<<i-1)];
            mn[i][j]=mn[i-1][j+(1<<i-1)];
        }
    }
    //print(n);
    qt.assign(k, vector<int>(n));
    for (int i=0; i<n; i++) {
        const auto l=lower_bound(e.begin(), e.end(), s[i])-e.begin(); //inc
        const auto r=upper_bound(e.begin(), e.end(), e[i])-e.begin(); //exc
        if (l>=r) qt[0][i]=i;
        else qt[0][i]=fmn(l, r);
    }
    //print(k);
    for (int i=1; i<k; i++) for (int j=0 ; j<n; j++) {
        qt[i][j]=qt[i-1][qt[i-1][j]];
    }
    //print(q);
    for (int i=0; i<q; ++i) {
        int a, b;
        cin>>a>>b;
        if (a==b) {
            cout<<"0\n";
            continue;
        }
        a=idx[--a], b=idx[--b];
        if (e[a]>=e[b]) {
            cout<<"impossible\n";
            continue;
        }
        int res=0;
        for (int j=k-1; j>=0; --j) if (s[qt[j][b]]>e[a]) {
            b=qt[j][b];
            res+=1<<j;
        }
        b=qt[0][b];
        ++res;
        if (e[a]>=s[b]) {
            cout<<++res<<'\n';
            continue;
        }
        cout<<"impossible\n";
    }
}

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