Submission #1120563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120563		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	1550 ms	26812 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 = 5e5+7;

int n,q,s[N],e[N],dp[N],pos[N],ans[N];
vector <pair <int,int>> f[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++) {
        s[i]=v[i-1].F.S, e[i]=v[i-1].F.F;
        pos[v[i-1].S]=i;
        // pos[i]=v[i-1].S;
    }
    for (int i=1;i<=q;i++) {
        int l,r;
        cin >> l >> r;
        l=pos[l], r=pos[r];
        f[l].eb(r,i);
    }
    vector <pair <int,int>> d;
    for (int i=1;i<=n;i++) {
        // cout << s[i] << ' ' << e[i] << ' ' << pos[i] << '\n';
        d.clear();
        dp[i]=0;
        d.eb(e[i],0);
        int R=0;
        for (auto now : f[i])
            R=max(R,now.F);
        for (int j=i+1;j<=R;j++) {
            int l=-1,r=d.size();
            while (l+1<r) {
                int mid=(l+r)/2;
                if (d[mid].F>=s[j])
                    r=mid;
                else
                    l=mid;
            }
            if (r==d.size() or d[r].S==INF)
                dp[j]=INF;
            else
                dp[j]=d[r].S+1;
            while (!d.empty() and d.back().S>=dp[j])
                d.pop_back();
            d.eb(e[j],dp[j]);
        }
        for (auto now : f[i]) {
            if (e[now.F]==e[i])
                ans[now.S]=1;
            else if (now.F<i or dp[now.F]==INF)
                ans[now.S]=-1;
            else
                ans[now.S]=dp[now.F];
        }
    }
    for (int i=1;i<=q;i++) {
        if (ans[i]==-1)
            cout << "impossible\n";
        else
            cout << ans[i] << '\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:83:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             if (r==d.size() or d[r].S==INF)
      |                 ~^~~~~~~~~~

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