oj.uz

Submission #887973

# Submission time Handle Problem Language Result Execution time Memory
887973 2023-12-15T16:04:49 Z teesla Event Hopping (BOI22_events) C++17
0 / 100
 463 ms 46564 KB 
#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;}

        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 385 ms 46404 KB Output is correct
3 Correct 407 ms 46564 KB Output is correct
4 Incorrect 463 ms 46304 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Incorrect 2 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Incorrect 2 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Incorrect 2 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 46384 KB Output is correct
2 Correct 410 ms 46312 KB Output is correct
3 Incorrect 451 ms 46272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 385 ms 46404 KB Output is correct
3 Correct 407 ms 46564 KB Output is correct
4 Incorrect 463 ms 46304 KB Output isn't correct
5 Halted 0 ms 0 KB -