oj.uz

Submission #637049

# Submission time Handle Problem Language Result Execution time Memory
637049 2022-08-31T10:56:02 Z DJeniUp Event Hopping (BOI22_events) C++17
20 / 100
 362 ms 29708 KB 
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 1000000000007
#define N 100007
#define endl '\n'
#define MOD 998244353

ll n,m,f[100007],a[100007],p[N][27];

pairll t[4*N];

priority_queue<pairll, vector<pairll>, greater<pairll> >q;

struct D{
    ll l,r,num;
}d[N];

bool mcp(D d1, D d2){
    return d1.r<d2.r;
}

void BT(ll x,ll l,ll r){
    if(l==r){
        t[x]={d[l].l,l};
        return ;
    }
    ll m1=(l+r)/2;
    BT(x*2+1,l,m1);
    BT(x*2+2,m1+1,r);
    if(t[x*2+1].fr<t[x*2+2].fr){
        t[x]=t[x*2+1];
    }else{
        t[x]=t[x*2+2];
    }
    return ;
}

pairll R(ll x,ll l,ll r,ll tl,ll tr){
    if(tr<tl)return {INF,0};
    if(r<tl || tr<l)return {INF,0};
    if(tl<=l && r<=tr)return t[x];
    ll m1=(l+r)/2;
    pairll m2=R(x*2+1,l,m1,tl,tr);
    pairll m3=R(x*2+2,m1+1,r,tl,tr);
    if(m2.fr<m3.fr)return m2;
    return m3;
}

pairll S(ll x,ll y){
    if(d[x].l<=d[y].r)return {x,0};
    ll g=0;
    for(int i=20;i>=0;i--){
        if(d[p[x][i]].l>d[y].r){
            g+=(1<<i);
            x=p[x][i];
        }
    }
    g++;
    x=p[x][0];
    return {x,g};
}
 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        ll x,y;
        cin>>x>>y;
        d[i]={x,y,i};
    }
    sort(d+1,d+1+n,mcp);
    for(int i=1;i<=n;i++){
        a[d[i].num]=i;
    }
    BT(0,1,n);
    for(int i=1;i<=n;i++){
        ll l=1;
        ll r=i;
        while(l<r){
            ll m1=(l+r)/2;
            if(d[m1].r<d[i].l)l=m1+1;
            else r=m1;
        }
        pairll m1=R(0,1,n,l,i-1);
        p[i][0]=m1.sc;
    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;i++){
        ll x,y;
        cin>>x>>y;
        
        x=a[x];
        y=a[y];
        if(d[y].r<d[x].r){
            cout<<"impossible"<<endl;
            continue;
        }
        pairll m1=S(y,x);
        swap(x,y);
        if(x==y)cout<<0<<endl;
        else if(d[m1.fr].r<d[y].r || d[m1.fr].l>d[y].r || m1.fr==0)cout<<"impossible"<<endl;
        else cout<<m1.sc+1<<endl;
    }
    
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 301 ms 29268 KB Output is correct
3 Correct 336 ms 29324 KB Output is correct
4 Correct 343 ms 29332 KB Output is correct
5 Correct 303 ms 29252 KB Output is correct
6 Correct 300 ms 29224 KB Output is correct
7 Correct 303 ms 29300 KB Output is correct
8 Incorrect 286 ms 29708 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 29212 KB Output is correct
2 Correct 302 ms 29248 KB Output is correct
3 Correct 322 ms 29248 KB Output is correct
4 Correct 297 ms 29676 KB Output is correct
5 Correct 338 ms 29644 KB Output is correct
6 Correct 362 ms 29420 KB Output is correct
7 Correct 343 ms 29372 KB Output is correct
8 Correct 326 ms 29516 KB Output is correct
9 Correct 120 ms 28748 KB Output is correct
10 Correct 320 ms 29092 KB Output is correct
11 Correct 306 ms 28848 KB Output is correct
12 Correct 309 ms 29072 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 301 ms 29268 KB Output is correct
3 Correct 336 ms 29324 KB Output is correct
4 Correct 343 ms 29332 KB Output is correct
5 Correct 303 ms 29252 KB Output is correct
6 Correct 300 ms 29224 KB Output is correct
7 Correct 303 ms 29300 KB Output is correct
8 Incorrect 286 ms 29708 KB Output isn't correct
9 Halted 0 ms 0 KB -