oj.uz

Submission #599471

# Submission time Handle Problem Language Result Execution time Memory
599471 2022-07-19T14:25:54 Z alexander707070 Event Hopping (BOI22_events) C++14
30 / 100
 350 ms 136936 KB 
#include<bits/stdc++.h>
#define MAXN 400007
using namespace std;

struct event{
    long long s;
    long long e;
    int id;

    inline friend bool operator < (event fr,event sc){
        if(fr.e!=sc.e)return fr.e<sc.e;
        return fr.s<=sc.s;
    }
};

int n,cnt,q,S,E,ans;
int st[MAXN],et[MAXN];
int parent[MAXN];
event e[MAXN];
vector<int> w;
map<int,int> mp;

pair<int,int> mins[8*MAXN];

pair<int,int> best(pair<int,int> fr,pair<int,int> sc){
    if(fr.second<=sc.second)return fr;
    return sc;
}

void update(int v,int l,int r,int pos,int val,int id){
    if(l==r){
        if(val<mins[v].second or val==10000000){
            mins[v]={id,val};
        }
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)update(2*v,l,tt,pos,val,id);
        else update(2*v+1,tt+1,r,pos,val,id);
        mins[v]=best(mins[2*v],mins[2*v+1]);
    }
}

pair<int,int> getmin(int v,int l,int r,int ll,int rr){
    if(ll>rr)return {0,100000000};
    if(l==ll and r==rr){
        return mins[v];
    }else{
        int tt=(l+r)/2;
        return best( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

int dp[MAXN][20];

void calc(){
    for(int f=0;f<20;f++){
        for(int i=1;i<=n;i++){
            if(f==0)dp[i][f]=parent[i];
            else dp[i][f]=dp[dp[i][f-1]][f-1];
        }
    }
}

int bin(int id,int id2){

    if(id==id2)return 0;
    if(et[id]<st[id2])return -1;
    if(et[id2]>et[id])return -1;
    if(et[id2]>=st[id])return 1;

    int res=0;
    for(int i=19;i>=0;i--){
        if(dp[id][i]!=0 and st[dp[id][i]]>et[id2]){
            id=dp[id][i];
            res+=(1<<i);
        }
    }

    if(parent[id]==0)return -1;
    if(parent[id]==id2)return res+1;
    return res+2;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>st[i]>>et[i];
        e[i]={st[i],et[i],i};
        w.push_back(e[i].s);
        w.push_back(e[i].e);
    }

    sort(w.begin(),w.end());
    for(int i=0;i<w.size();i++){
        if(i>0 and w[i]!=w[i-1])cnt++;
        mp[w[i]]=cnt;
    }

    for(int i=1;i<=n;i++){
        e[i].s=mp[e[i].s];
        e[i].e=mp[e[i].e];
    }

    for(int i=0;i<=cnt;i++){
        update(1,0,cnt,i,10000000,0);
    }

    sort(e+1,e+n+1);
    for(int i=1;i<=n;i++){
        if(e[i].s<0 or e[i].s>cnt or e[i].e<0 or e[i].e>cnt)return 0;
        parent[e[i].id]=getmin(1,0,cnt,e[i].s,e[i].e).first;
        update(1,0,cnt,e[i].e,e[i].s,e[i].id);
    }
    calc();

    for(int i=1;i<=q;i++){
        cin>>S>>E;
        ans=bin(E,S);
        if(ans==-1)cout<<"impossible\n";
        else cout<<ans<<"\n";
    }


    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 190 ms 19784 KB Output is correct
3 Correct 223 ms 19796 KB Output is correct
4 Correct 222 ms 19784 KB Output is correct
5 Correct 197 ms 20304 KB Output is correct
6 Correct 248 ms 20788 KB Output is correct
7 Correct 243 ms 20904 KB Output is correct
8 Correct 317 ms 27080 KB Output is correct
9 Correct 229 ms 27096 KB Output is correct
10 Correct 220 ms 20132 KB Output is correct
11 Correct 205 ms 24152 KB Output is correct
12 Correct 154 ms 20332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Runtime error 166 ms 136936 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Runtime error 166 ms 136936 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Runtime error 166 ms 136936 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 19844 KB Output is correct
2 Correct 245 ms 19836 KB Output is correct
3 Correct 262 ms 19796 KB Output is correct
4 Correct 227 ms 27000 KB Output is correct
5 Correct 282 ms 20124 KB Output is correct
6 Correct 253 ms 26744 KB Output is correct
7 Correct 264 ms 26608 KB Output is correct
8 Correct 308 ms 26756 KB Output is correct
9 Correct 224 ms 25996 KB Output is correct
10 Correct 284 ms 26340 KB Output is correct
11 Correct 350 ms 26180 KB Output is correct
12 Correct 255 ms 26380 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 190 ms 19784 KB Output is correct
3 Correct 223 ms 19796 KB Output is correct
4 Correct 222 ms 19784 KB Output is correct
5 Correct 197 ms 20304 KB Output is correct
6 Correct 248 ms 20788 KB Output is correct
7 Correct 243 ms 20904 KB Output is correct
8 Correct 317 ms 27080 KB Output is correct
9 Correct 229 ms 27096 KB Output is correct
10 Correct 220 ms 20132 KB Output is correct
11 Correct 205 ms 24152 KB Output is correct
12 Correct 154 ms 20332 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Runtime error 166 ms 136936 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -