oj.uz

Submission #599500

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

    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<=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 732 ms 340 KB Output is correct
2 Correct 865 ms 18580 KB Output is correct
3 Correct 894 ms 18516 KB Output is correct
4 Correct 931 ms 18436 KB Output is correct
5 Correct 898 ms 19112 KB Output is correct
6 Correct 897 ms 19768 KB Output is correct
7 Correct 932 ms 19912 KB Output is correct
8 Correct 883 ms 24452 KB Output is correct
9 Correct 898 ms 24436 KB Output is correct
10 Correct 912 ms 18816 KB Output is correct
11 Correct 909 ms 21136 KB Output is correct
12 Correct 827 ms 18956 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 340 KB Output is correct
2 Correct 721 ms 340 KB Output is correct
3 Correct 712 ms 460 KB Output is correct
4 Correct 719 ms 432 KB Output is correct
5 Correct 733 ms 432 KB Output is correct
6 Correct 729 ms 432 KB Output is correct
7 Correct 744 ms 488 KB Output is correct
8 Correct 752 ms 484 KB Output is correct
9 Runtime error 156 ms 136976 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 715 ms 340 KB Output is correct
2 Correct 721 ms 340 KB Output is correct
3 Correct 712 ms 460 KB Output is correct
4 Correct 719 ms 432 KB Output is correct
5 Correct 733 ms 432 KB Output is correct
6 Correct 729 ms 432 KB Output is correct
7 Correct 744 ms 488 KB Output is correct
8 Correct 752 ms 484 KB Output is correct
9 Runtime error 156 ms 136976 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 715 ms 340 KB Output is correct
2 Correct 721 ms 340 KB Output is correct
3 Correct 712 ms 460 KB Output is correct
4 Correct 719 ms 432 KB Output is correct
5 Correct 733 ms 432 KB Output is correct
6 Correct 729 ms 432 KB Output is correct
7 Correct 744 ms 488 KB Output is correct
8 Correct 752 ms 484 KB Output is correct
9 Runtime error 156 ms 136976 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 892 ms 18580 KB Output is correct
2 Correct 911 ms 18576 KB Output is correct
3 Correct 924 ms 18452 KB Output is correct
4 Correct 962 ms 24440 KB Output is correct
5 Correct 925 ms 18888 KB Output is correct
6 Correct 986 ms 24188 KB Output is correct
7 Correct 1069 ms 24180 KB Output is correct
8 Correct 1054 ms 24220 KB Output is correct
9 Execution timed out 1584 ms 15608 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 340 KB Output is correct
2 Correct 865 ms 18580 KB Output is correct
3 Correct 894 ms 18516 KB Output is correct
4 Correct 931 ms 18436 KB Output is correct
5 Correct 898 ms 19112 KB Output is correct
6 Correct 897 ms 19768 KB Output is correct
7 Correct 932 ms 19912 KB Output is correct
8 Correct 883 ms 24452 KB Output is correct
9 Correct 898 ms 24436 KB Output is correct
10 Correct 912 ms 18816 KB Output is correct
11 Correct 909 ms 21136 KB Output is correct
12 Correct 827 ms 18956 KB Output is correct
13 Correct 715 ms 340 KB Output is correct
14 Correct 721 ms 340 KB Output is correct
15 Correct 712 ms 460 KB Output is correct
16 Correct 719 ms 432 KB Output is correct
17 Correct 733 ms 432 KB Output is correct
18 Correct 729 ms 432 KB Output is correct
19 Correct 744 ms 488 KB Output is correct
20 Correct 752 ms 484 KB Output is correct
21 Runtime error 156 ms 136976 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -