oj.uz

Submission #599876

# Submission time Handle Problem Language Result Execution time Memory
599876 2022-07-20T05:10:04 Z isaachew Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 3520 KB 
#include <bits/stdc++.h>
/*
 The whole event space is a DAG
 
 Calculate the minimum switching to get from time A to B
 
 Get from an event to another
 
 Event to event
 Every event is either completely contained in another, or not
 Completely contained = directed edge from contained
 Not = earlier end to later end
 An O(E) = O(N^2) should get 35 points
 Use RQTree to get minimum switches by sorting by end time; O(NQ log N)
 You cannot switch to an event with same end time; waste
 ST5: Earlier start time = earlier end time
 Go backwards and use segment tree
 */

int n,q;
std::vector<int> rqtree;
std::vector<int> endpoints;
int query(int l,int r,int nl=0,int nr=n+1,int ni=0){
    //std::cout<<nl<<"/"<<nr<<'\n';
    if(nl+1>=nr){
        if(l<=endpoints[nl]&&r>endpoints[nl])return rqtree[ni];
        return 1000000001;
    }
    if(l>=endpoints[nr]||r<=endpoints[nl])return 1000000001;
    if(l<=endpoints[nl]&&r>=endpoints[nr]){
        return rqtree[ni];
    }
    int nm=(nl+nr)/2;
    return std::min(query(l,r,nl,nm,ni+1),query(l,r,nm,nr,ni+2*(nm-nl)));
}
void update(int loc,int val,int nl=0,int nr=n+1,int ni=0){
    //std::cout<<"upd "<<nl<<' '<<nr<<'\n';
    if(nl+1>=nr){
        if(loc==endpoints[nl])rqtree[ni]=std::min(rqtree[ni],val);
        return;
    }
    int nm=(nl+nr)/2;
    if(loc<endpoints[nm]){
        rqtree[ni]=std::min(rqtree[ni],val);
        update(loc,val,nl,nm,ni+1);
    }else{
        rqtree[ni]=std::min(rqtree[ni],val);
        update(loc,val,nm,nr,ni+2*(nm-nl));
    }
}
std::vector<std::pair<int,int>> events;
std::vector<std::pair<int,int>> queries;
std::vector<int> s_events;
std::vector<int> i_s_events;
std::vector<int> out_arr;
int main(){
    std::cin>>n>>q;
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        events.push_back({a,b});
        endpoints.push_back(b);
        s_events.push_back(i);
    }
    
    endpoints.push_back(0);
    endpoints.push_back(1000000001);
    std::sort(endpoints.begin(),endpoints.end());
      
    std::sort(s_events.begin(),s_events.end(),[](int a,int b){return events[a].second==events[b].second?events[a].first<events[b].first:events[a].second<events[b].second;});
    i_s_events.resize(n,-1);
    for(int i=0;i<n;i++){
        i_s_events[s_events[i]]=i;
    }
    
    for(int i=0;i<q;i++){
        int start,end;
        rqtree.clear();
        rqtree.resize(2*n+5,1000000001);
        std::cin>>start>>end;
        start--;end--;//1 indexing
        if(start==end){
            std::cout<<"0\n";
            continue;
        }
        int s_epos=i_s_events[start];
        int e_epos=i_s_events[end];
        if(events[start].second>events[end].second){
            std::cout<<"impossible\n";
            continue;
        }
        update(events[start].second,0);//0 switches
        for(int k=s_epos+1;k<=e_epos;k++){
            //std::cout<<"ev from "<<events[s_events[k]].first<<" to "<<events[s_events[k]].second<<'\n';
            int evnum=s_events[k];
            int les=query(events[evnum].first,events[evnum].second+1);
            //std::cout<<les+1<<";\n";
            update(events[evnum].second,les+1);
            if(k==e_epos){
                if(les>1000000000){
                    std::cout<<"impossible\n";
                }else{
                    std::cout<<les+1<<'\n';
                }
            }
        }
        //std::cout<<"finish q\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1587 ms 3516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 7 ms 212 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 7 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 20 ms 212 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 4 ms 212 KB Output is correct
15 Correct 7 ms 212 KB Output is correct
16 Correct 7 ms 212 KB Output is correct
17 Correct 5 ms 212 KB Output is correct
18 Correct 8 ms 212 KB Output is correct
19 Execution timed out 1555 ms 484 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 19 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 7 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 19 ms 212 KB Output is correct
13 Correct 4 ms 212 KB Output is correct
14 Correct 4 ms 212 KB Output is correct
15 Correct 4 ms 212 KB Output is correct
16 Correct 9 ms 212 KB Output is correct
17 Correct 7 ms 212 KB Output is correct
18 Correct 10 ms 212 KB Output is correct
19 Execution timed out 1590 ms 3520 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 3504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1587 ms 3516 KB Time limit exceeded
3 Halted 0 ms 0 KB -