oj.uz

Submission #580689

# Submission time Handle Problem Language Result Execution time Memory
580689 2022-06-21T16:19:20 Z jasmin Event Hopping (BOI22_events) C++17
0 / 100
 414 ms 43740 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int inf=1e18;

struct segtree{
    vector<pair<int,int> > tree;

    segtree(int n){
        tree.resize(n*4, {inf, -1});
    }

    pair<int,int> merge(pair<int,int> a, pair<int,int> b){
        if(a.first<b.first){
            return a;
        }
        return b;
    }

    pair<int,int> update(int l, int r, int v, int x, int val, int ind){
        if(r<=x || x<l) return tree[v];
        if(l+1==r){
            return tree[v]=merge(tree[v], {val, ind});
        }
        int m=l+(r-l)/2;
        return tree[v]=merge(update(l, m, v*2+1, x, val, ind), update(m, r, v*2+2, x, val, ind));
    }
    pair<int,int> query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return {inf, -1};
        if(ql<=l && r<=qr) return tree[v];
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

int dist(int a, int b, vector<vector<int> >& up, vector<int>& s, vector<int>& t){
    if(a==b) return 0;
    if(t[a]<t[b]) return -1;
    if(s[a]<t[b]){
        return 1;
    }

    int l=25;
    int ans=0;
    for(int i=l-1; i>=0; i--){
        if(up[a][i]!=-1 && t[b]<s[up[a][i]]){
            a=up[a][i];
            ans+=(1<<i);
        }
    }

    if(up[a][0]!=-1){
        return ans+2;
    }
    return -1;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> s(n);
    vector<int> t(n);
    set<int> nums;
    nums.insert(inf);
    for(int i=0; i<n; i++){
        cin >> s[i] >> t[i];
        nums.insert(s[i]);
        nums.insert(t[i]);
    }
    int g=nums.size();
    map<int,int> num; int ind=0;
    for(auto e: nums){
        num[e]=ind;
        ind++;
    }

    segtree seg(g);
    for(int i=0; i<n; i++){
        seg.update(0, g, 0, num[t[i]], s[i], i);
    }
    vector<int> p(n, -1);
    for(int i=0; i<n; i++){
        auto x=seg.query(0, g, 0, num[s[i]], num[t[i]]+1);
        if(x.first<s[i]){
            p[i]=x.second;
        }
    }

    int l=25;
    vector<vector<int> > up(n, vector<int> (l, -1));
    for(int i=0; i<n; i++){
        up[i][0]=p[i];
    }
    for(int x=1; x<l; x++){
        for(int i=0; i<n; i++){
            if(up[i][x-1]!=-1){
                up[i][x]=up[up[i][x-1]][x-1];
            }
        }
    }

    for(int i=0; i<q; i++){
        int a, b;
        cin >> a >> b;
        int ans=dist(b-1, a-1, up, s, t);
        if(ans==-1){
            cout << "impossible\n";
        }
        else{
            cout << dist(b-1, a-1, up, s, t) << "\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 312 ms 43280 KB Output is correct
3 Correct 351 ms 43668 KB Output is correct
4 Incorrect 408 ms 43740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 43140 KB Output is correct
2 Correct 367 ms 43176 KB Output is correct
3 Incorrect 414 ms 43136 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 212 KB Output is correct
2 Correct 312 ms 43280 KB Output is correct
3 Correct 351 ms 43668 KB Output is correct
4 Incorrect 408 ms 43740 KB Output isn't correct
5 Halted 0 ms 0 KB -