oj.uz

Submission #637045

# Submission time Handle Problem Language Result Execution time Memory
637045 2022-08-31T10:50:35 Z DJeniUp Event Hopping (BOI22_events) C++17
20 / 100
 364 ms 32884 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];
        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 310 ms 32412 KB Output is correct
3 Correct 298 ms 32376 KB Output is correct
4 Correct 341 ms 32300 KB Output is correct
5 Correct 303 ms 32412 KB Output is correct
6 Correct 351 ms 32504 KB Output is correct
7 Correct 315 ms 32648 KB Output is correct
8 Incorrect 283 ms 32856 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 312 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 580 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Incorrect 2 ms 584 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 312 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 580 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Incorrect 2 ms 584 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 312 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 580 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Incorrect 2 ms 584 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 320 ms 32276 KB Output is correct
2 Correct 326 ms 32332 KB Output is correct
3 Correct 326 ms 32312 KB Output is correct
4 Correct 296 ms 32884 KB Output is correct
5 Correct 350 ms 32636 KB Output is correct
6 Correct 361 ms 32408 KB Output is correct
7 Correct 364 ms 32444 KB Output is correct
8 Correct 360 ms 32536 KB Output is correct
9 Correct 120 ms 30516 KB Output is correct
10 Correct 300 ms 32040 KB Output is correct
11 Correct 327 ms 31860 KB Output is correct
12 Correct 302 ms 32048 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 310 ms 32412 KB Output is correct
3 Correct 298 ms 32376 KB Output is correct
4 Correct 341 ms 32300 KB Output is correct
5 Correct 303 ms 32412 KB Output is correct
6 Correct 351 ms 32504 KB Output is correct
7 Correct 315 ms 32648 KB Output is correct
8 Incorrect 283 ms 32856 KB Output isn't correct
9 Halted 0 ms 0 KB -