Submission #599907

#	Time	Username	Problem	Language	Result	Execution time	Memory
599907		isaachew	Event Hopping (BOI22_events)	C++17	40 / 100	1583 ms	3780 KiB

events

#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 (start time is increasing)
 Go backwards and use segment tree
 
 ST4: O(NQ), not O(NQ log N)
 
 Go backwards; min switches from is increasing
 You now have to go from a time to an event
 Switches can be calculated by using min number of switches for every time
 
 If the start (end) event was not a key event, add 1
 
 Edges split and join; an event inside another is just a join
 Select a chain of events with minimum switches
 
 If there was a chain that connected two events, it would have to be part of the main chain
 
 1         2        3           4  5  6 7
        \                            /
      S  1            2             3E
 1         2          3             4 5 6
 
 Update a chain?
 If the start is moved forward, the chain stays
 If the end is moved backward, the chain ?
 If start is moved backwards, extend the chain
 */

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;
        std::cin>>start>>end;
        start--,end--;
        int cswc=0;//count
        int cset=1000000001;//end time
        int nset=1000000001;//next end time (first start)
        cset=nset=events[end].first;
        int f_index=std::upper_bound(endpoints.begin(),endpoints.end(),events[end].second)-endpoints.begin()-2;
        int s_index=i_s_events[start];
        //std::cout<<s_index<<" to "<<f_index<<'\n';
        //std::cout<<events[end].second<<"?\n";
        if(events[end].second<events[start].second){
            cswc=-1;
        }
        if(start==end){
            std::cout<<"0\n";
            continue;
        }
        for(int p=f_index;p>=s_index;p--){
            //if(p==i_s_events[end])continue;
            int ceid=s_events[p];
            //std::cout<<ceid<<";\n";
            if(events[ceid].second<nset){
                cswc=-1;
                break;
            }else if(events[ceid].second<cset){
                //std::cout<<"inc\n";
                cswc++;
                cset=nset;
            }else{
                
            }
            nset=std::min(nset,events[ceid].first);
        }
        if(cswc==-1){
            std::cout<<"impossible\n";
        }else{
            std::cout<<cswc+1<<'\n';
        }
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30