oj.uz

Submission #599431

# Submission time Handle Problem Language Result Execution time Memory
599431 2022-07-19T14:04:22 Z alexander707070 Event Hopping (BOI22_events) C++17
30 / 100
 370 ms 152884 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 pos[MAXN],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];
bool li[MAXN][20];

int ff(int x,int p){
    if(x==0)return 0;
    if(p==0)return parent[x];

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p]=ff(ff(x,p-1),p-1);
    return dp[x][p];
}

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(ff(id,i)!=0 and st[ff(id,i)]>et[id2]){
            id=ff(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];
        pos[e[i].id]=i;
    }

    for(int i=0;i<=cnt;i++){
        update(1,0,cnt,i,10000000,0);
    }

    sort(e+1,e+n+1);
    for(int i=1;i<=n;i++){
        parent[e[i].id]=getmin(1,0,cnt,e[i].s,e[i].e).first;
        update(1,0,cnt,e[i].e,e[i].s,e[i].id);
    }

    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:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 178 ms 22276 KB Output is correct
3 Correct 268 ms 22084 KB Output is correct
4 Correct 352 ms 22276 KB Output is correct
5 Correct 258 ms 22688 KB Output is correct
6 Correct 269 ms 23144 KB Output is correct
7 Correct 250 ms 23344 KB Output is correct
8 Correct 195 ms 22452 KB Output is correct
9 Correct 205 ms 22396 KB Output is correct
10 Correct 282 ms 22588 KB Output is correct
11 Correct 253 ms 26608 KB Output is correct
12 Correct 138 ms 12832 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 22192 KB Output is correct
2 Correct 273 ms 22208 KB Output is correct
3 Correct 370 ms 22144 KB Output is correct
4 Correct 191 ms 22436 KB Output is correct
5 Correct 291 ms 22468 KB Output is correct
6 Correct 316 ms 29064 KB Output is correct
7 Correct 299 ms 29076 KB Output is correct
8 Correct 279 ms 29128 KB Output is correct
9 Correct 209 ms 18532 KB Output is correct
10 Correct 268 ms 28632 KB Output is correct
11 Correct 240 ms 23328 KB Output is correct
12 Correct 293 ms 28708 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 178 ms 22276 KB Output is correct
3 Correct 268 ms 22084 KB Output is correct
4 Correct 352 ms 22276 KB Output is correct
5 Correct 258 ms 22688 KB Output is correct
6 Correct 269 ms 23144 KB Output is correct
7 Correct 250 ms 23344 KB Output is correct
8 Correct 195 ms 22452 KB Output is correct
9 Correct 205 ms 22396 KB Output is correct
10 Correct 282 ms 22588 KB Output is correct
11 Correct 253 ms 26608 KB Output is correct
12 Correct 138 ms 12832 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 596 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 2 ms 468 KB Output is correct
21 Runtime error 172 ms 152884 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -