oj.uz

Submission #637059

# Submission time Handle Problem Language Result Execution time Memory
637059 2022-08-31T11:24:07 Z DJeniUp Event Hopping (BOI22_events) C++17
20 / 100
 197 ms 29840 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];
        }
    }
    return {x,g};
}
 
int main()
{
    //cin>>n>>m;
    scanf("%lld %lld", &n, &m);
    for(int i=1;i<=n;i++){
        ll x,y;
        //cin>>x>>y;
        scanf("%lld %lld", &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);
        if(m1.fr>=d[i].l)p[i][0]=0;
        else 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;
        scanf("%lld %lld", &x, &y);
        
        x=a[x];
        y=a[y];
        if(d[y].r<d[x].r){
            //cout<<"impossible"<<endl;
            printf("impossible\n");
            continue;
        }
        pairll m1=S(y,x);
        swap(x,y);
        if(x==y)printf("0\n");
        else {
            ll res=INF;
            ll h=m1.fr;
            ll g=m1.sc;
            for(int i=1;i<=10;i++){
                g++;
                if(d[h].l<=d[y].r && d[y].r<=d[h].r)res=min(res,g);
                h=p[h][0];
            }
            if(res==INF)cout<<"impossible"<<endl;
            else cout<<res<<endl;
        }
    }
    
    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%lld %lld", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
events.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
events.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 108 ms 29308 KB Output is correct
3 Correct 120 ms 29392 KB Output is correct
4 Correct 127 ms 29388 KB Output is correct
5 Correct 143 ms 29340 KB Output is correct
6 Correct 109 ms 29452 KB Output is correct
7 Correct 110 ms 29492 KB Output is correct
8 Incorrect 100 ms 29800 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 1 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 512 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 1 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 512 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 1 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 512 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 115 ms 29384 KB Output is correct
2 Correct 116 ms 29276 KB Output is correct
3 Correct 125 ms 29440 KB Output is correct
4 Correct 94 ms 29776 KB Output is correct
5 Correct 160 ms 29840 KB Output is correct
6 Correct 197 ms 29516 KB Output is correct
7 Correct 190 ms 29576 KB Output is correct
8 Correct 136 ms 29664 KB Output is correct
9 Correct 72 ms 28764 KB Output is correct
10 Correct 120 ms 29188 KB Output is correct
11 Correct 118 ms 28980 KB Output is correct
12 Correct 117 ms 29132 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 108 ms 29308 KB Output is correct
3 Correct 120 ms 29392 KB Output is correct
4 Correct 127 ms 29388 KB Output is correct
5 Correct 143 ms 29340 KB Output is correct
6 Correct 109 ms 29452 KB Output is correct
7 Correct 110 ms 29492 KB Output is correct
8 Incorrect 100 ms 29800 KB Output isn't correct
9 Halted 0 ms 0 KB -