Submission #779777

#	Time	Username	Problem	Language	Result	Execution time	Memory
779777		anton	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	178 ms	46824 KiB

railway_trip

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

const int bar = (1<<16);
const int INF= (1<<29)-1;

struct Node{
    pii min;
    pii max;

    static Node e(){
        return Node{pii(INF, -1), pii(-INF, -1)};
    }
};

struct Tree{
    Node tree[2*bar];
    Tree(vector<Node>& v){
        build(v, 0, v.size()-1, 1);
    }

    static Node merge(Node a, Node b){
        Node res;
        if(a.min<=b.min){
            res.min = a.min;
        }
        else{
            res.min = b.min;
        }
        if(a.max>=b.max){
            res.max = a.max;
        }
        else{
            res.max= b.max;
        }
        return res;
    }


    void build(vector<Node>& v, int lt, int rt, int t){
        if(lt==rt){
            tree[t] = v[lt];
        }
        else{
            int mid = (lt+rt)/2;

            build(v, lt, mid, t*2);
            build(v, mid+1, rt, t*2+1);
            tree[t] = merge(tree[t*2], tree[t*2+1]);
        }
    }

    Node range_q(int l, int r, int lt, int rt, int t){
        if(rt<l || r< lt){
            return Node::e();
        }
        else if(l<= lt && rt <= r){
            return tree[t];
        }
        else{
            int mid = (rt+lt)/2;

            return merge(range_q(l, r, lt, mid, t*2),range_q(l, r, mid+1, rt, t*2+1));
        }
    }
};

struct Line{
    int l, r;
    int dest;
    bool right;
    int pre_pos, post_pos;
    Node transition;
};
vector<Line> lines;
vector<Node> pre;
vector<Node> post;
vector<Node> im;

int main(){
    int n, k, m;
    cin>>n>>k>>m;

    

    for(int i = 0; i<m; i++){
        int a, b;
        cin>>a>>b;
        a--;
        b--;

        Line l;
        if(a<b){
            l.l = a;
            l.r = min(a+k-1, b);
            l.dest =b;
            l.right = true;
            pre.push_back(Node{pii(l.r, i), pii(b, i)});
            post.push_back(Node{pii(l.r, i), pii(b, i)});
        }
        else{
            l.l = max(a-k+1, b);
            l.r = a;
            l.dest =b;
            l.right = false;
            pre.push_back(Node{pii(b, i), pii(l.l, i)});
            post.push_back(Node{pii(b, i), pii(l.l, i)});
        }
        lines.push_back(l);
    }

    for(int i = 0; i<n; i++){
        Line l;
        l.l = i;
        l.r= i;
        l.dest=i;
        l.transition = Node{pii(i, i+m), pii(i, i+m)};
        lines.push_back(l);
        l.right = true;
        pre.push_back(l.transition);
        post.push_back(l.transition);
    }
    m+=n;

    auto pre_cmp = [&](Node a, Node b){
        return lines[a.min.second].l<lines[b.min.second].l;
    };
    auto post_cmp = [&](Node a, Node b){
        return lines[a.min.second].r<lines[b.min.second].r;
    };


    sort(pre.begin(), pre.end(), pre_cmp);
    sort(post.begin(), post.end(), post_cmp);

    //cout<<"done "<<endl;

    im.resize(n);
    set<pii> ms;
    int pre_id= 0, post_id = 0;
    for(int i = 0; i<n; i++){
        while(post_id<post.size() && lines[post[post_id].min.second].r ==i-1){
            ms.erase(pii(lines[post[post_id].min.second].dest, post[post_id].min.second));
            post_id++;
        }
        while(pre_id<pre.size() && lines[pre[pre_id].min.second].l ==i){
            ms.insert(pii(lines[pre[pre_id].min.second].dest, pre[pre_id].min.second));
            pre_id++;
        }
        

        im[i]= Node{pii(i, i+m-n), pii(i, i+m-n)};
        if(ms.size()>0){

            //cout<<(*ms.begin()).first<<" "<<(*ms.begin()).second<<" "<<(--ms.end())->first<<" "<<(--ms.end())->second<<endl;
            im[i] = Tree::merge(im[i], Node{*ms.begin(), *(--ms.end())});
        }
        //cout<<"im "<<i<<" "<<im[i].min.first<<" "<<im[i].max.first<<endl;
        
        //cout<<"im "<<i<<" "<<im[i].min.second<<" "<<im[i].max.second<<endl;
    }
    //cout<<"hello"<<endl;

    for(int i = 0; i<m; i++){
        lines[pre[i].min.second].pre_pos = i;
        lines[post[i].min.second].post_pos = i;
    }
    vector<int> first_oc_pre(n);
    for(int i =m-1; i>=0; i--){
        first_oc_pre[lines[pre[i].min.second].l] = i;
    }
    vector<int> last_oc_post(n);
    for(int i =0; i<m; i++){
        last_oc_post[lines[post[i].min.second].r] = i;
    }

    Tree pre_tree = Tree(pre);
    Tree post_tree = Tree(post);
    

    for(int i = 0; i<m; i++){
        //cout<<lines[i].l<<" "<<lines[i].r<<" "<<lines[i].dest<<endl;
        if(lines[i].right){
            pii inter = pii(first_oc_pre[lines[i].l], lines[i].pre_pos);

            for(int step = (1<<20); step>=1; step/=2){
                if(inter.second + step<m){
                    auto next = inter.second +step;
                    if(lines[pre[next].min.second].l<=lines[i].dest){
                        inter.second += step;
                    }

                }
            }

            //cout<<inter.first<<" "<<inter.second<<endl;

            lines[i].transition = pre_tree.range_q(inter.first, inter.second, 0, m-1, 1);
            for(int j= inter.first; j<=inter.second; j++){
                //cout<<lines[pre[j].min.second].l<<" "<<lines[pre[j].min.second].r<<" | ";
            }
            //cout<<endl;
        }
        else{
            pii inter = pii(lines[i].post_pos, last_oc_post[lines[i].r]);

            for(int step = (1<<20); step>=1; step/=2){
                if(inter.first -step>=0){
                    auto next = inter.first -step;
                    if(lines[post[next].min.second].r>= lines[i].dest){
                        inter.first -= step;
                    }
                }
            }

            //cout<<inter.first<<" "<<inter.second<<endl;

            lines[i].transition = post_tree.range_q(inter.first, inter.second, 0, m-1, 1);
        }
        //cout<<"transition "<<lines[i].transition.min.first<<" "<<lines[i].transition.max.first<<endl;
        //cout<<"transition "<<lines[i].transition.min.second<<" "<<lines[i].transition.max.second<<endl;
    }
    
    
    vector<vector<Node>> tr(18, vector<Node>(m));

    for(int i = 0; i<m; i++){
        tr[0][i] = lines[i].transition;
        //tr[0][i] = pre[lines[i].pre_pos]; 
    }

    for(int step = 1; step<18; step++){
        for(int i = 0; i<m; i++){

            int a = tr[step-1][i].min.second;
            int b = tr[step-1][i].max.second;
            tr[step][i] = Tree::merge(tr[step-1][a], tr[step-1][b]);
        }
    }


    //cout<<"displaying depth 0"<<endl;
    for(int i = 0; i<m; i++){
        //cout<<lines[i].transition.min.second<<" "<<lines[i].transition.max.second<<endl;
        //cout<<lines[i].l<<" "<<lines[i].r<<" "<<lines[i].dest<<" "<<tr[0][i].min.first<<" "<<tr[0][i].max.first<<endl;
    }

    int q;
    cin>>q;

    //cout<<"q: "<<q<<endl;
    for(int i = 0; i<q; i++){
        int a, b;
        cin>>a>>b;
        a--;
        b--;

        int res= 1;

        if(a==b){
            cout<<0<<endl;
            continue;
        }

        Node cur = im[a];
        if(b>=cur.min.first && b<= cur.max.first){
            cout<<res<<endl;
            continue;
        }

        if(cur.min.second ==-1&&cur.max.second ==-1){
            cout<<-1<<endl;
            continue;
        }

        //cout<<"anwsering"<<endl;

        
        //cout<<cur.min.first<<" "<<cur.max.first<<endl;
        //cout<<cur.min.second<<" "<<cur.max.second<<endl;

        for(int step = 17; step>=0; step--){
            int cost = (1<<step);
            Node next;

            Node min_d =tr[step][cur.min.second];
            //cout<<"min_d "<<cur.min.second<<" "<<min_d.min.first<<" "<<min_d.max.first<<endl;
            Node max_d = tr[step][cur.max.second];
            //cout<<"max_d "<<cur.max.second<<" "<<max_d.min.first<<" "<<max_d.max.first<<endl;
            next = Tree::merge(min_d, max_d);

            if(b<next.min.first || b> next.max.first){
                cur = next;
                res += cost;
                //cout<<"taking"<<endl;
            }
            //cout<<cur.min.first<<" "<<cur.max.first<<endl;
            //cout<<cur.min.second<<" "<<cur.max.second<<endl;
        }

        Node next;

        Node min_d =tr[0][cur.min.second];
        Node max_d = tr[0][cur.max.second];
        next = Tree::merge(min_d, max_d);

        if(b<next.min.first || b> next.max.first){
            cout<<-1<<endl;
            continue;
        }
        else{
            
            //cout<<"final : "<<next.min.first<<" "<<next.max.first<<endl;
            cout<<res+1<<endl;
            continue;
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55