Submission #1104108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104108		andrewp	Event Hopping (BOI22_events)	C++14	30 / 100	147 ms	31932 KiB

events

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std; 
using ll=int64_t;
using pii=pair<int,int>; 
using pll=pair<int,int>;
#define all(x) x.begin(),x.end()
#define raint(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define se second
#define mp make_pair 
#define dbg(x) cerr<<#x<<": "<<x<<'\n';
#define dbga(A,l_,r_){cerr<<#A<<": ";for(int i_=l_;i_<=r_;i_++)cerr<<A[i_]<<' ';cerr<<'\n';}
#define dbgv(a_){cerr<<#a_<<": ";for(auto x_:a_) cerr<<x_<<' ';cerr<<'\n';}
const int N=1e5+50;
int n,q,l[N],r[N],ord[N],id[N],prv[N],lg[N],jmp[N][20];
pii up[N][20];
bool cmp(int i,int j){
    if(r[i]==r[j]) return l[i]<l[j];
    return r[i]<r[j];
}
pii Get(int l,int r){
    int k=lg[r-l+1]; 
    return min(up[l][k],up[r-(1<<k)+1][k]);
}
int main(){ 
    scanf("%d%d",&n,&q); 
    vector<int> cmprs; 
    for(int i=0;i<n;i++){
        scanf("%d%d",&l[i],&r[i]);
        cmprs.pb(l[i]); cmprs.pb(r[i]);
    }
    sort(all(cmprs)); cmprs.erase(unique(all(cmprs)),cmprs.end());
    for(int i=0;i<n;i++){
        l[i]=lower_bound(all(cmprs),l[i])-cmprs.begin();
        r[i]=lower_bound(all(cmprs),r[i])-cmprs.begin();
    }  
    iota(ord,ord+n,0);
    sort(ord,ord+n,cmp); 
    for(int i=0;i<n;i++) id[ord[i]]=i;
    vector<int> swl(n),swr(n);
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1; 
    for(int i=0;i<n;i++) swl[i]=l[ord[i]],swr[i]=r[ord[i]];
    for(int i=0;i<n;i++) l[i]=swl[i],r[i]=swr[i]; 
    for(int i=0;i<n;i++) up[i][0]=mp(l[i],i);
    for(int j=1;j<20;j++) for(int i=0;i+(1<<j)<=n;i++){
        up[i][j]=min(up[i][j-1],up[i+(1<<(j-1))][j-1]);
    } 
    for(int i=0;i<n;i++){
        int bot=0,top=i;
        prv[i]=i;
        while(bot<=top){
            int mid=(bot+top)/2;
            if(r[mid]>=l[i]){
                prv[i]=mid;
                top=mid-1;
            }else bot=mid+1;
        }
    }  
    for(int i=0;i<n;i++) jmp[i][0]=prv[i];
    for(int j=1;j<20;j++) for(int i=0;i<n;i++){
        jmp[i][j]=jmp[Get(jmp[i][j-1],i).se][j-1];
    }
    while(q--){
        int s,e; scanf("%d%d",&s,&e);
        --s,--e; s=id[s],e=id[e];
        if(s>e){printf("impossible\n");continue;}
        if(s==e){printf("0\n");continue;}
        if(r[s]>=l[e]&&r[s]<=r[e]){printf("1\n");continue;} 
        int ans=0;
        for(int i=19;i>=0;i--){
            if(jmp[e][i]>s){
                ans+=(1<<i);
                e=Get(jmp[e][i],e).se;
            }
        }
        if(jmp[e][0]<=s) ans++;
        else{printf("impossible\n");continue;}
        printf("%d\n",ans);
    }
    return 0;       
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
events.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d%d",&l[i],&r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:67:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         int s,e; scanf("%d%d",&s,&e);
      |                  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30