oj.uz

Submission #599492

# Submission time Handle Problem Language Result Execution time Memory
599492 2022-07-19T14:36:46 Z alexander707070 Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 136916 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);
        mins[i]={0,10000000};
    }

    sort(e+1,e+n+1);
    for(int i=1;i<=n;i++){
        pair<int,int> sol={0,100000000};
        for(int f=e[i].s;f<=e[i].e;f++){
            sol=best(sol,mins[f]);
        }
        //parent[e[i].id]=getmin(1,0,cnt,e[i].s,e[i].e).first;
        parent[e[i].id]=sol.first;
        //update(1,0,cnt,e[i].e,e[i].s,e[i].id);
        mins[e[i].e]=best(mins[e[i].e],{e[i].id,e[i].s});
    }
    calc();

    for(int i=1;i<=1000000000;i++);

    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 1 ms 340 KB Output is correct
2 Correct 158 ms 18664 KB Output is correct
3 Correct 157 ms 18492 KB Output is correct
4 Correct 205 ms 18504 KB Output is correct
5 Correct 195 ms 19168 KB Output is correct
6 Correct 178 ms 19684 KB Output is correct
7 Correct 230 ms 19904 KB Output is correct
8 Correct 170 ms 24488 KB Output is correct
9 Correct 155 ms 24440 KB Output is correct
10 Correct 206 ms 18904 KB Output is correct
11 Correct 194 ms 21164 KB Output is correct
12 Correct 95 ms 19020 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Runtime error 191 ms 136916 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Runtime error 191 ms 136916 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Runtime error 191 ms 136916 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 18560 KB Output is correct
2 Correct 194 ms 18516 KB Output is correct
3 Correct 201 ms 18468 KB Output is correct
4 Correct 162 ms 24536 KB Output is correct
5 Correct 216 ms 18996 KB Output is correct
6 Correct 247 ms 24136 KB Output is correct
7 Correct 201 ms 24156 KB Output is correct
8 Correct 194 ms 24320 KB Output is correct
9 Execution timed out 1588 ms 15508 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 158 ms 18664 KB Output is correct
3 Correct 157 ms 18492 KB Output is correct
4 Correct 205 ms 18504 KB Output is correct
5 Correct 195 ms 19168 KB Output is correct
6 Correct 178 ms 19684 KB Output is correct
7 Correct 230 ms 19904 KB Output is correct
8 Correct 170 ms 24488 KB Output is correct
9 Correct 155 ms 24440 KB Output is correct
10 Correct 206 ms 18904 KB Output is correct
11 Correct 194 ms 21164 KB Output is correct
12 Correct 95 ms 19020 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Runtime error 191 ms 136916 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -