제출 #581120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581120		jasmin	Event Hopping (BOI22_events)	C++17	100 / 100	663 ms	61452 KiB

events

#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+=((int)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;
    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 << ans << "\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