oj.uz

답안 #780031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780031 2023-07-12T05:51:26 Z anton Railway Trip 2 (JOI22_ho_t4) C++17
11 / 100
 2000 ms 72736 KB 
#include<bits/stdc++.h>

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

const int bar = (1<<19);
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{
    vector<Node> tree;
    Tree(vector<Node>& v){
        tree.resize(2*bar);
        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(1, 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<m+1; 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[0][a], tr[0][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 = m; step>=0; step--){
            int cost = 1;
            Node next;

            Node min_d =tr[0][cur.min.second];
            //cout<<"min_d "<<cur.min.second<<" "<<min_d.min.first<<" "<<min_d.max.first<<endl;
            Node max_d = tr[0][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;
        }
    }


}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         while(post_id<post.size() && lines[post[post_id].min.second].r ==i-1){
      |               ~~~~~~~^~~~~~~~~~~~
Main.cpp:149:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         while(pre_id<pre.size() && lines[pre[pre_id].min.second].l ==i){
      |               ~~~~~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33236 KB Output is correct
2 Correct 18 ms 33200 KB Output is correct
3 Correct 20 ms 33160 KB Output is correct
4 Correct 15 ms 33196 KB Output is correct
5 Correct 16 ms 33128 KB Output is correct
6 Correct 16 ms 33252 KB Output is correct
7 Correct 17 ms 33236 KB Output is correct
8 Correct 15 ms 33236 KB Output is correct
9 Correct 14 ms 33204 KB Output is correct
10 Correct 17 ms 33036 KB Output is correct
11 Correct 14 ms 33200 KB Output is correct
12 Incorrect 14 ms 33236 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33236 KB Output is correct
2 Correct 18 ms 33200 KB Output is correct
3 Correct 20 ms 33160 KB Output is correct
4 Correct 15 ms 33196 KB Output is correct
5 Correct 16 ms 33128 KB Output is correct
6 Correct 16 ms 33252 KB Output is correct
7 Correct 17 ms 33236 KB Output is correct
8 Correct 15 ms 33236 KB Output is correct
9 Correct 14 ms 33204 KB Output is correct
10 Correct 17 ms 33036 KB Output is correct
11 Correct 14 ms 33200 KB Output is correct
12 Incorrect 14 ms 33236 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 54852 KB Output is correct
2 Correct 309 ms 54620 KB Output is correct
3 Correct 354 ms 56584 KB Output is correct
4 Correct 243 ms 54016 KB Output is correct
5 Correct 953 ms 69792 KB Output is correct
6 Correct 797 ms 68300 KB Output is correct
7 Correct 468 ms 72736 KB Output is correct
8 Correct 401 ms 57848 KB Output is correct
9 Correct 397 ms 58484 KB Output is correct
10 Correct 865 ms 68288 KB Output is correct
11 Correct 861 ms 68284 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2055 ms 56900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2081 ms 70064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33236 KB Output is correct
2 Correct 18 ms 33200 KB Output is correct
3 Correct 20 ms 33160 KB Output is correct
4 Correct 15 ms 33196 KB Output is correct
5 Correct 16 ms 33128 KB Output is correct
6 Correct 16 ms 33252 KB Output is correct
7 Correct 17 ms 33236 KB Output is correct
8 Correct 15 ms 33236 KB Output is correct
9 Correct 14 ms 33204 KB Output is correct
10 Correct 17 ms 33036 KB Output is correct
11 Correct 14 ms 33200 KB Output is correct
12 Incorrect 14 ms 33236 KB Output isn't correct
13 Halted 0 ms 0 KB -