oj.uz

Submission #599502

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

    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<=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 782 ms 340 KB Output is correct
2 Correct 917 ms 18560 KB Output is correct
3 Correct 909 ms 18560 KB Output is correct
4 Correct 971 ms 18560 KB Output is correct
5 Correct 948 ms 19120 KB Output is correct
6 Correct 947 ms 19584 KB Output is correct
7 Correct 945 ms 19896 KB Output is correct
8 Correct 886 ms 24528 KB Output is correct
9 Correct 882 ms 24544 KB Output is correct
10 Correct 907 ms 18936 KB Output is correct
11 Correct 910 ms 21068 KB Output is correct
12 Correct 822 ms 19072 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 340 KB Output is correct
2 Correct 726 ms 340 KB Output is correct
3 Correct 747 ms 420 KB Output is correct
4 Correct 715 ms 428 KB Output is correct
5 Correct 723 ms 460 KB Output is correct
6 Correct 719 ms 432 KB Output is correct
7 Correct 726 ms 468 KB Output is correct
8 Correct 728 ms 468 KB Output is correct
9 Runtime error 930 ms 137008 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 714 ms 340 KB Output is correct
2 Correct 726 ms 340 KB Output is correct
3 Correct 747 ms 420 KB Output is correct
4 Correct 715 ms 428 KB Output is correct
5 Correct 723 ms 460 KB Output is correct
6 Correct 719 ms 432 KB Output is correct
7 Correct 726 ms 468 KB Output is correct
8 Correct 728 ms 468 KB Output is correct
9 Runtime error 930 ms 137008 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 714 ms 340 KB Output is correct
2 Correct 726 ms 340 KB Output is correct
3 Correct 747 ms 420 KB Output is correct
4 Correct 715 ms 428 KB Output is correct
5 Correct 723 ms 460 KB Output is correct
6 Correct 719 ms 432 KB Output is correct
7 Correct 726 ms 468 KB Output is correct
8 Correct 728 ms 468 KB Output is correct
9 Runtime error 930 ms 137008 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 895 ms 18564 KB Output is correct
2 Correct 890 ms 18560 KB Output is correct
3 Correct 920 ms 18532 KB Output is correct
4 Correct 896 ms 24532 KB Output is correct
5 Correct 923 ms 18988 KB Output is correct
6 Correct 950 ms 24160 KB Output is correct
7 Correct 972 ms 24156 KB Output is correct
8 Correct 947 ms 24280 KB Output is correct
9 Execution timed out 1588 ms 15576 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 340 KB Output is correct
2 Correct 917 ms 18560 KB Output is correct
3 Correct 909 ms 18560 KB Output is correct
4 Correct 971 ms 18560 KB Output is correct
5 Correct 948 ms 19120 KB Output is correct
6 Correct 947 ms 19584 KB Output is correct
7 Correct 945 ms 19896 KB Output is correct
8 Correct 886 ms 24528 KB Output is correct
9 Correct 882 ms 24544 KB Output is correct
10 Correct 907 ms 18936 KB Output is correct
11 Correct 910 ms 21068 KB Output is correct
12 Correct 822 ms 19072 KB Output is correct
13 Correct 714 ms 340 KB Output is correct
14 Correct 726 ms 340 KB Output is correct
15 Correct 747 ms 420 KB Output is correct
16 Correct 715 ms 428 KB Output is correct
17 Correct 723 ms 460 KB Output is correct
18 Correct 719 ms 432 KB Output is correct
19 Correct 726 ms 468 KB Output is correct
20 Correct 728 ms 468 KB Output is correct
21 Runtime error 930 ms 137008 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -