Submission #1121055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121055		vjudge1	Event Hopping (BOI22_events)	C++17	100 / 100	147 ms	24856 KiB

events

// Bolatulu
#include <bits/stdc++.h>
// #include <art.h>

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/

typedef long long ll;
typedef unsigned long long ull; 
typedef double db;
#define pb push_back
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,md
#define TR v+v+1,md+1,tr
#define Tl t[v].l,tl,md
#define Tr t[v].r,md+1,tr
#define all(x) (x).begin(),(x).end()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define int long long
// #define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

const ll INF = 1e18+7;
const int N = 1e5+7;

int n,q,s[N],e[N],p[N][20],pos[N];

void solve() {
    cin >> n >> q;
    vector <pair <pair <int,int>,int>> v;
    for (int i=1;i<=n;i++) {
        cin >> s[i] >> e[i];
        v.pb({{e[i],s[i]},i});
    }
    sort(all(v));
    for (int i=1;i<=n;i++) {
        e[i]=v[i-1].F.F, s[i]=v[i-1].F.S;
        // cout << e[i] << '\n';
        pos[v[i-1].S]=i;
        // pos[i]=v[i-1].S;
    }
    vector <int> d;
    d.pb(1);
    for (int i=0;i<20;i++)
        p[1][i]=-1;
    for (int i=2;i<=n;i++) {
        int l=-1,r=d.size();
        while (l+1<r) {
            int mid=(l+r)/2;
            if (e[d[mid]]>=s[i])
                r=mid;
            else
                l=mid;
        }
        if (r==d.size())
            p[i][0]=-1;
        else
            p[i][0]=d[r];
        // cout << pos[p[i][0]] << ' ' << pos[i] << ' ' << e[i] << '\n';
        for (int j=1;j<20;j++) {
            if (p[i][j-1]==-1)
                p[i][j]=-1;
            else
                p[i][j]=p[p[i][j-1]][j-1];
        }
        while (!d.empty() and s[d.back()]>=s[i])
            d.pop_back();
        d.pb(i);
    }
    while (q--) {
        int l,r;
        cin >> l >> r;
        l=pos[l], r=pos[r];
        if (l==r) {
            cout << 0 << '\n';
            continue;
        }
        if (l>r) {
            if (e[r]==e[l])
                cout << 1 << '\n';
            else
                cout << "impossible\n";
            continue;
        }
        if (s[r]<=e[l]) {
            cout << 1 << '\n';
            continue;
        }
        int ans=0;
        bool ok=false;
        for (int i=19;i>=0;i--) {
            if (p[r][i]!=-1 and s[p[r][i]]>e[l]) {
                ans+=(1<<i);
                r=p[r][i];
            }
        }
        ans++;
        if (p[r][0]==-1) {
            cout << "impossible\n";
            continue;
        }
        r=p[r][0];
        // cout << r << ' ' << l << ' ' << s[r] << ' ' << e[l] << '\n';
        if (s[r]<=e[l])
            cout << ans+1 << '\n';
        else
            cout << "impossible\n";
    }
}   

signed main() {
    // file("jenga");
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int test = 1;
    // cin >> test;
    while (test--) {
        solve();
        if (test)
            cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'void solve()':
events.cpp:72:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if (r==d.size())
      |             ~^~~~~~~~~~
events.cpp:107:14: warning: unused variable 'ok' [-Wunused-variable]
  107 |         bool ok=false;
      |              ^~

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