Submission #972825

#	Time	Username	Problem	Language	Result	Execution time	Memory
972825		idas	Event Hopping (BOI22_events)	C++11	20 / 100	344 ms	37276 KiB

events

#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) int((x).size())
#define pb push_back
#define s second
#define f first

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int INF=1e9;

const int N=1e5+10, L=18;
int n, q, s[N], e[N], bl[L][N];
map<int, int> c; int idx;
pii t[8*N];

void upd(int p, pii x, int l=1, int r=idx, int id=1)
{
    if(l==r){
        t[id]=x;
        return;
    }
    int m=(l+r)/2;
    if(p<=m) upd(p, x, l, m, id*2);
    else upd(p, x, m+1, r, id*2+1);
    t[id]=min(t[id*2], t[id*2+1]);
}

pii get(int x, int y, int l=1, int r=idx, int id=1)
{
    if(r<x||l>y) return {INF,INF};
    if(x<=l&&r<=y) return t[id];
    int m=(l+r)/2;
    return min(
        get(x, y, l, m, id*2),
        get(x, y, m+1, r, id*2+1)
    );
}

void build()
{
    FOR(i, 1, L)
    {
        FOR(j, 0, n)
        {
            bl[i][j]=bl[i-1][bl[i-1][j]];
        }
    }
}

int ans(int a, int b)
{
    if(a==b) return 0;
    if(s[b]<=e[a] && e[a]<=e[b]) return 1;
    if(e[a]>e[b]) return INF;

    int ret=0;
    for(int i=L-1; i>=0; i--){
        int k=bl[i][b];

        if(s[k]<=e[a]) continue;

        b=k; ret+=1<<i;
    }

    b=bl[0][b]; ret++;

    if(s[b]<=e[a]) return ret+1;

    return INF;
}

int main()
{
    FAST_IO;
    cin >> n >> q;
    set<int> dif;
    FOR(i, 0, n)
    {
        cin >> s[i] >> e[i];
        dif.insert(s[i]);
        dif.insert(e[i]);
    }

    for(auto it : dif) c[it]=++idx;

    FOR(i, 0, 8*N) t[i]={INF,INF};

    FOR(i, 0, n)
    {
        upd(c[e[i]], {s[i],i});
    }

    FOR(i, 0, n)
    {
        pii ret=get(c[s[i]], c[e[i]]);
        int in=ret.s;
        bl[0][i]=in;
//        cout << i << ": " << in << endl;
    }

    build();

    while(q--){
        int a, b; cin >> a >> b; --a; --b;
        int k=ans(a, b);
        if(k==INF){
            cout << "impossible\n";
        }
        else{
            cout << k << '\n';
        }
    }
}
/*
2 1
1 4
2 3
1 2

5 2
1 3
2 4
4 7
7 9
3 7

tst1:
8 1
1 3
3 6
3 7
3 8
3 9
3 10
10 10
1 10

tst2:
3 1
3 4
1 6
4 9

tst3:
5 1
1 8
1 2
2 3
3 4
6 7

tst4:
7 1
1 4
2 4
3 4
4 5
4 6
4 7
7 9

tst5:
5 1
1 2
2 5
2 6
5 8
6 8

tst6:
5 1
1 2
2 3
3 4
4 9
2 8
*/

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