Submission #887979

#	Time	Username	Problem	Language	Result	Execution time	Memory
887979		teesla	Event Hopping (BOI22_events)	C++17	100 / 100	516 ms	56484 KiB

events

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int maxx = 1e9+5;
const int LOG = 20;

vector<ii> tree;

void update(int pos, int i, int f, int idx, int val, int id){

    if(i == f){
        tree[pos] =min(tree[pos], {val,id});
        return;
    }
    int meio = (i+f)/2;

    if(idx <= meio) update(2*pos+1, i, meio, idx, val, id);
    else update(2*pos+2, meio + 1, f, idx, val, id);

    tree[pos] = min(tree[2*pos+1], tree[2*pos+2]);
    return;
}

ii query(int pos, int i, int f, int l, int r){

    if(l<=i and f<=r) return tree[pos];

    int meio = (i+f)/2;
    ii aa = {maxx, -1};

    if(l <=meio) aa = min(aa, query(2*pos+1, i, meio, l, r));
    if( r > meio) aa = min(aa, query(2*pos+2, meio + 1, f, l, r));

    return aa;
}

int main(){

    int n,q; cin >> n >> q;
    vector<ii> v(n+2);
    vector<iii> event;
    tree.resize(8*n, {maxx, -1});

    set<int> S;

    for(int i=1; i<=n; i++){
        int s,e; cin >> s >> e;
        v[i] = {s,e};
        S.insert(s);
        S.insert(e);
    }

    map<int,int> COMP;

    for(auto i: S){
        COMP[i] = COMP.size();
    }

    for(auto &[a,b]: v) {a = COMP[a]; b = COMP[b];}

    for(int i=1; i<=n; i++){ event.push_back({v[i].first, {0,i}}); event.push_back({v[i].second, {1,i}}); update(0,0,COMP.size(), v[i].second, v[i].first, i);}

    sort(event.begin(), event.end());
    set<ii> aux;

    vector sparse1(n+2, vector (LOG,0));

    for(auto [t,b]: event){
        auto [type,idx] = b;
        
        if(!type) aux.insert({v[idx].second, idx});
        else{
            auto [maior, i] = *prev(aux.end());
            sparse1[idx][0] = i;
            aux.erase({t, idx});
        }
    }

    for(int i=1; i<LOG; i++) for(int j = 1; j<=n; j++){

        sparse1[j][i] = sparse1[sparse1[j][i-1]][i-1];
    }

    

    vector sparse2(n+2, vector (LOG,0));

    for(int i=1; i<=n; i++){
        sparse2[i][0] = query(0,0,COMP.size(), v[i].first, v[i].second).second;
    }
    

    for(int i=1; i<LOG; i++) for(int j = 1; j<=n; j++){

        sparse2[j][i] = sparse2[sparse2[j][i-1]][i-1];
    }


    while(q--){

        int s,e; cin >> s >> e;

        if(s==e){cout << 0 << endl; continue;}

        if(v[e].first <= v[s].second and v[s].second <= v[e].second){cout << 1 << endl; continue;}

        int ss = s, ee = e;
        int qnt = 0;

        for(int i = LOG - 1; i>=0; i--){
            int idx = sparse1[ss][i];

            if(v[idx].second >= v[e].first) continue;
            ss = idx;
            qnt += (1<<i);
        }

        for(int i = LOG - 1; i>=0; i--){
            int idx = sparse2[ee][i];

            if(v[idx].first > v[ss].second){
                ee = idx;
                qnt += (1<<i);
            }
        }

        ee = sparse2[ee][0];

        qnt++;

        if(v[ee].first <= v[ss].second and v[ee].second >= v[ss].second) cout << qnt+1 << endl;
        else cout << "impossible\n";
    }

}

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