Submission #1287016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287016		cowkim	Event Hopping (BOI22_events)	C++20	100 / 100	585 ms	253544 KiB

events

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iomanip>
#define ll long long
#define endl "\n"
using namespace std;
struct smallerToLargerStruct{
    int size = 0;
    int lazy = 0;
    //första är för slutiden av starteventet
    map<int,vector<pair<int,int>>> daMap;
};
void add(smallerToLargerStruct* stl, int s, int id){
    stl->size += 1;
    pair<int,int> par = {id, -stl->lazy};
    stl->daMap[s].push_back(par);
}
smallerToLargerStruct* combine(smallerToLargerStruct* a, smallerToLargerStruct* b){
    if(a==b) return a;
    if(a->size < b->size) swap(a,b);
    a->size += b->size;
    int diff = b->lazy - a->lazy;
    for(auto item : b->daMap){
        for(auto query : item.second){
            query.second += diff;
            a->daMap[item.first].push_back(query);
        }
    }
    return a;
}
struct edge{
    int start;
    int end;
    int eventid;
    smallerToLargerStruct* vals = new smallerToLargerStruct();
};
bool edgeEndCompare(const edge& a, const edge& b){
    return a.end < b.end;
}
bool edgeStartCompare(const edge& a, const edge& b){
    return a.start < b.start;
}
edge* getMin(edge* a, edge* b){
    if(a == nullptr) return b;
    if(b == nullptr) return a;
    return a->start < b->start ? a:b;
}
struct segNode{
    int nodel,noder;
    segNode* lNode = nullptr;
    segNode* rNode = nullptr;
    edge* minStart = nullptr;
    segNode(int l, int r){
        nodel = l;
        noder = r;
    }
    void extend(){
        if(lNode == nullptr){
            //cout << nodel << " " << noder << endl;
            int mid = nodel + (noder-nodel)/2;
            lNode = new segNode(nodel,mid);
            rNode = new segNode(mid+1,noder);
        }
    }
    edge* update(int pos,edge* change){
        if(pos < nodel || noder < pos) return minStart;
        if(nodel == noder) return minStart = getMin(minStart,change);
        extend();
        return minStart = getMin(lNode->update(pos,change),rNode->update(pos,change));
    }
    edge* querie(int l, int r){
        if(r < nodel || noder < l) return nullptr;
        if(l <= nodel && noder <= r) return minStart;
        extend();   
        return getMin(lNode->querie(l,r), rNode->querie(l,r));
    }
};
vector<int> ans;
void getAllAns(int s, smallerToLargerStruct* stl){
    for(auto it = stl->daMap.lower_bound(s); it != stl->daMap.end();){
        for(auto par : it->second){
            par.second += stl->lazy;
            ans[par.first] = par.second+1;
        }
        it = stl->daMap.erase(it);
    }
}
int main(){
    int n, q;
    cin >> n >> q;
    vector<edge> events(n);
    ans.resize(q,-1);
    for(int i = 0; i<n; i++){
        cin >> events[i].start >> events[i].end;
        events[i].eventid = i;
    }
    for(int i = 0; i<q; i++){
        int si, ei;
        cin >> si >> ei;
        si--;
        ei--;
        if(si == ei){
            ans[i] = 0;
            continue;
        }
        if(events[si].end > events[ei].end){
            ans[i] = -1;
            continue;
        } 
        add(events[ei].vals,events[si].end,i);
    }
    sort(events.begin(),events.end(),edgeStartCompare);
    segNode daSeg(1,1e9);
    for(int i = 0; i< events.size();i++){
        daSeg.update(events[i].end,&events[i]);
    }
    for(int i = n-1;i >= 0; i--){
        getAllAns(events[i].start,events[i].vals);
        edge* maxVal = daSeg.querie(events[i].start,events[i].end);
        if(maxVal == nullptr) continue;
        events[i].vals->lazy++;
        maxVal->vals = combine(maxVal->vals,events[i].vals);
    }
    for(int i = 0; i<ans.size();i++){
        if(ans[i] == -1) cout << "impossible" << endl;
        else cout << ans[i] << endl;
    }
    return 0;
}

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