oj.uz

Submission #599499

# Submission time Handle Problem Language Result Execution time Memory
599499 2022-07-19T14:40:08 Z alexander707070 Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 136928 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(long long i=1;i<=100000000;i++){
        S=(E+3928)%30009; E=(S+2472)%20300;    
    }

    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 722 ms 348 KB Output is correct
2 Correct 871 ms 18484 KB Output is correct
3 Correct 877 ms 18612 KB Output is correct
4 Correct 932 ms 18488 KB Output is correct
5 Correct 913 ms 19152 KB Output is correct
6 Correct 933 ms 19652 KB Output is correct
7 Correct 895 ms 19832 KB Output is correct
8 Correct 900 ms 24480 KB Output is correct
9 Correct 900 ms 24524 KB Output is correct
10 Correct 929 ms 18876 KB Output is correct
11 Correct 908 ms 21060 KB Output is correct
12 Correct 820 ms 19000 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 344 KB Output is correct
2 Correct 722 ms 348 KB Output is correct
3 Correct 741 ms 516 KB Output is correct
4 Correct 738 ms 520 KB Output is correct
5 Correct 729 ms 524 KB Output is correct
6 Correct 731 ms 468 KB Output is correct
7 Correct 743 ms 576 KB Output is correct
8 Correct 737 ms 576 KB Output is correct
9 Runtime error 159 ms 136928 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 735 ms 344 KB Output is correct
2 Correct 722 ms 348 KB Output is correct
3 Correct 741 ms 516 KB Output is correct
4 Correct 738 ms 520 KB Output is correct
5 Correct 729 ms 524 KB Output is correct
6 Correct 731 ms 468 KB Output is correct
7 Correct 743 ms 576 KB Output is correct
8 Correct 737 ms 576 KB Output is correct
9 Runtime error 159 ms 136928 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 735 ms 344 KB Output is correct
2 Correct 722 ms 348 KB Output is correct
3 Correct 741 ms 516 KB Output is correct
4 Correct 738 ms 520 KB Output is correct
5 Correct 729 ms 524 KB Output is correct
6 Correct 731 ms 468 KB Output is correct
7 Correct 743 ms 576 KB Output is correct
8 Correct 737 ms 576 KB Output is correct
9 Runtime error 159 ms 136928 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 900 ms 18552 KB Output is correct
2 Correct 891 ms 18564 KB Output is correct
3 Correct 912 ms 18488 KB Output is correct
4 Correct 927 ms 24480 KB Output is correct
5 Correct 921 ms 19040 KB Output is correct
6 Correct 941 ms 24180 KB Output is correct
7 Correct 944 ms 24084 KB Output is correct
8 Correct 941 ms 24220 KB Output is correct
9 Execution timed out 1589 ms 15568 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 348 KB Output is correct
2 Correct 871 ms 18484 KB Output is correct
3 Correct 877 ms 18612 KB Output is correct
4 Correct 932 ms 18488 KB Output is correct
5 Correct 913 ms 19152 KB Output is correct
6 Correct 933 ms 19652 KB Output is correct
7 Correct 895 ms 19832 KB Output is correct
8 Correct 900 ms 24480 KB Output is correct
9 Correct 900 ms 24524 KB Output is correct
10 Correct 929 ms 18876 KB Output is correct
11 Correct 908 ms 21060 KB Output is correct
12 Correct 820 ms 19000 KB Output is correct
13 Correct 735 ms 344 KB Output is correct
14 Correct 722 ms 348 KB Output is correct
15 Correct 741 ms 516 KB Output is correct
16 Correct 738 ms 520 KB Output is correct
17 Correct 729 ms 524 KB Output is correct
18 Correct 731 ms 468 KB Output is correct
19 Correct 743 ms 576 KB Output is correct
20 Correct 737 ms 576 KB Output is correct
21 Runtime error 159 ms 136928 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -