oj.uz

Submission #637047

# Submission time Handle Problem Language Result Execution time Memory
637047 2022-08-31T10:55:23 Z DJeniUp Event Hopping (BOI22_events) C++17
20 / 100
 368 ms 30004 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)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 323 ms 29244 KB Output is correct
3 Correct 300 ms 29256 KB Output is correct
4 Correct 334 ms 29356 KB Output is correct
5 Correct 311 ms 29264 KB Output is correct
6 Correct 335 ms 29332 KB Output is correct
7 Correct 296 ms 29260 KB Output is correct
8 Incorrect 278 ms 29772 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 301 ms 29188 KB Output is correct
2 Correct 327 ms 29380 KB Output is correct
3 Correct 333 ms 29188 KB Output is correct
4 Correct 307 ms 30004 KB Output is correct
5 Correct 348 ms 29540 KB Output is correct
6 Correct 368 ms 29492 KB Output is correct
7 Correct 351 ms 29372 KB Output is correct
8 Correct 334 ms 29596 KB Output is correct
9 Correct 137 ms 28664 KB Output is correct
10 Correct 309 ms 29008 KB Output is correct
11 Correct 333 ms 28740 KB Output is correct
12 Correct 311 ms 29056 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 323 ms 29244 KB Output is correct
3 Correct 300 ms 29256 KB Output is correct
4 Correct 334 ms 29356 KB Output is correct
5 Correct 311 ms 29264 KB Output is correct
6 Correct 335 ms 29332 KB Output is correct
7 Correct 296 ms 29260 KB Output is correct
8 Incorrect 278 ms 29772 KB Output isn't correct
9 Halted 0 ms 0 KB -