oj.uz

Submission #637054

# Submission time Handle Problem Language Result Execution time Memory
637054 2022-08-31T11:15:57 Z DJeniUp Event Hopping (BOI22_events) C++17
20 / 100
 155 ms 29776 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;
    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 if(d[m1.fr].r<d[y].r || d[m1.fr].l>d[y].r || m1.fr==0)printf("impossible\n");
        else printf("%lld\n", m1.sc+1);
    }
    
    return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 112 ms 29272 KB Output is correct
3 Correct 105 ms 29176 KB Output is correct
4 Correct 122 ms 29256 KB Output is correct
5 Correct 108 ms 29300 KB Output is correct
6 Correct 106 ms 29324 KB Output is correct
7 Correct 108 ms 29380 KB Output is correct
8 Incorrect 84 ms 29652 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 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Incorrect 1 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 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Incorrect 1 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 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Incorrect 1 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 108 ms 29160 KB Output is correct
2 Correct 109 ms 29260 KB Output is correct
3 Correct 125 ms 29224 KB Output is correct
4 Correct 91 ms 29776 KB Output is correct
5 Correct 143 ms 29528 KB Output is correct
6 Correct 155 ms 29592 KB Output is correct
7 Correct 147 ms 29308 KB Output is correct
8 Correct 132 ms 29608 KB Output is correct
9 Correct 74 ms 28616 KB Output is correct
10 Correct 132 ms 29132 KB Output is correct
11 Correct 115 ms 28748 KB Output is correct
12 Correct 122 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 112 ms 29272 KB Output is correct
3 Correct 105 ms 29176 KB Output is correct
4 Correct 122 ms 29256 KB Output is correct
5 Correct 108 ms 29300 KB Output is correct
6 Correct 106 ms 29324 KB Output is correct
7 Correct 108 ms 29380 KB Output is correct
8 Incorrect 84 ms 29652 KB Output isn't correct
9 Halted 0 ms 0 KB -