Submission #887986

#	Time	Username	Problem	Language	Result	Execution time	Memory
887986		qrno	Event Hopping (BOI22_events)	C++17	100 / 100	510 ms	53696 KiB

events

// CODIGO DA ESTELA!!!!! (eu ajudei talvez)

#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 && 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