oj.uz

Submission #599494

# Submission time Handle Problem Language Result Execution time Memory
599494 2022-07-19T14:38:16 Z alexander707070 Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 137020 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<=10000000000;i++){
        S=E-1; E=S+1;   
    }

    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 191 ms 18496 KB Output is correct
3 Correct 182 ms 18552 KB Output is correct
4 Correct 236 ms 18564 KB Output is correct
5 Correct 187 ms 19148 KB Output is correct
6 Correct 210 ms 19656 KB Output is correct
7 Correct 201 ms 19868 KB Output is correct
8 Correct 182 ms 24488 KB Output is correct
9 Correct 207 ms 24444 KB Output is correct
10 Correct 184 ms 18884 KB Output is correct
11 Correct 183 ms 21036 KB Output is correct
12 Correct 107 ms 19072 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 2 ms 468 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 2 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 173 ms 137020 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 2 ms 468 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 2 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 173 ms 137020 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 2 ms 468 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 2 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 173 ms 137020 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 190 ms 18564 KB Output is correct
2 Correct 203 ms 18548 KB Output is correct
3 Correct 239 ms 18504 KB Output is correct
4 Correct 176 ms 24532 KB Output is correct
5 Correct 180 ms 18940 KB Output is correct
6 Correct 237 ms 24172 KB Output is correct
7 Correct 213 ms 24168 KB Output is correct
8 Correct 264 ms 24236 KB Output is correct
9 Execution timed out 1560 ms 15592 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 191 ms 18496 KB Output is correct
3 Correct 182 ms 18552 KB Output is correct
4 Correct 236 ms 18564 KB Output is correct
5 Correct 187 ms 19148 KB Output is correct
6 Correct 210 ms 19656 KB Output is correct
7 Correct 201 ms 19868 KB Output is correct
8 Correct 182 ms 24488 KB Output is correct
9 Correct 207 ms 24444 KB Output is correct
10 Correct 184 ms 18884 KB Output is correct
11 Correct 183 ms 21036 KB Output is correct
12 Correct 107 ms 19072 KB Output is correct
13 Correct 1 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 444 KB Output is correct
17 Correct 2 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 173 ms 137020 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -