Submission #1120657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120657		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	78 ms	16180 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 = 2e5+7;
const int M = 1e4+7;

int n,q,s[N],e[N],pos[N];
bool u[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));
    vector <pair <pair <int,int>,int>> nv;
    for (int i=0;i<n-1;i++) {
        if (v[i].F.F<v[i+1].F.S or v[i].F.S<v[i+1].F.S)
            nv.pb(v[i]);
        else
            u[v[i].S]=1;
    }
    v=nv;
    set <int> s;
    for (int i=0;i<n;i++) {
        pos[v[i].S]=i+1;
        if (i>0 and v[i].F.S>v[i-1].F.F)
            s.ins(i);
    }
    while (q--) {
        int l,r;
        cin >> l >> r;
        if (l==r) {
            cout << 0 << '\n';
            continue;
        }
        l=pos[l],r=pos[r];
        int z=u[l]+u[r];
        auto it=s.upper_bound(l);
        if (l==r)
            cout << 0 << '\n';
        else if (e[l]==e[r])
            cout << 1 << '\n';
        else if (l>r or (it!=s.end() and *it<=r))
            cout << "impossible\n";
        else
            cout << r-l+z << '\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;
}

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