oj.uz

답안 #779786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779786 2023-07-11T20:15:25 Z anton Railway Trip 2 (JOI22_ho_t4) C++17
46 / 100
 1101 ms 162628 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);

    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){
            im[i] = Tree::merge(im[i], Node{*ms.begin(), *(--ms.end())});
        }
    }
    //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;
                    }

                }
            }

            lines[i].transition = pre_tree.range_q(inter.first, inter.second, 0, m-1, 1);
        }
        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;
                    }
                }
            }

            lines[i].transition = post_tree.range_q(inter.first, inter.second, 0, m-1, 1);
        }
    }
    
    
    vector<vector<Node>> tr(20, 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<20; 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]);
        }
    }

    int q;
    cin>>q;

    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;
        }

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

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

            if(b<next.min.first || b> next.max.first){
                cur = next;
                res += cost;
               
            }

        }
        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<<res+1<<endl;
            continue;
        }
    }
}

Compilation message

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

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33364 KB Output is correct
2 Correct 17 ms 33292 KB Output is correct
3 Correct 16 ms 33392 KB Output is correct
4 Correct 16 ms 33364 KB Output is correct
5 Correct 16 ms 33364 KB Output is correct
6 Correct 16 ms 33360 KB Output is correct
7 Correct 16 ms 33364 KB Output is correct
8 Correct 15 ms 33404 KB Output is correct
9 Correct 18 ms 33356 KB Output is correct
10 Correct 17 ms 33084 KB Output is correct
11 Correct 15 ms 33380 KB Output is correct
12 Incorrect 15 ms 33408 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33364 KB Output is correct
2 Correct 17 ms 33292 KB Output is correct
3 Correct 16 ms 33392 KB Output is correct
4 Correct 16 ms 33364 KB Output is correct
5 Correct 16 ms 33364 KB Output is correct
6 Correct 16 ms 33360 KB Output is correct
7 Correct 16 ms 33364 KB Output is correct
8 Correct 15 ms 33404 KB Output is correct
9 Correct 18 ms 33356 KB Output is correct
10 Correct 17 ms 33084 KB Output is correct
11 Correct 15 ms 33380 KB Output is correct
12 Incorrect 15 ms 33408 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 107824 KB Output is correct
2 Correct 302 ms 108116 KB Output is correct
3 Correct 354 ms 114960 KB Output is correct
4 Correct 276 ms 105900 KB Output is correct
5 Correct 912 ms 158944 KB Output is correct
6 Correct 876 ms 157508 KB Output is correct
7 Correct 496 ms 161908 KB Output is correct
8 Correct 432 ms 117172 KB Output is correct
9 Correct 463 ms 118020 KB Output is correct
10 Correct 940 ms 157568 KB Output is correct
11 Correct 1036 ms 157516 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 109336 KB Output is correct
2 Correct 1002 ms 159836 KB Output is correct
3 Correct 574 ms 117188 KB Output is correct
4 Correct 639 ms 162628 KB Output is correct
5 Correct 965 ms 161600 KB Output is correct
6 Correct 1026 ms 161536 KB Output is correct
7 Incorrect 1101 ms 158248 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 930 ms 157232 KB Output is correct
2 Correct 474 ms 117288 KB Output is correct
3 Correct 333 ms 98476 KB Output is correct
4 Correct 224 ms 84496 KB Output is correct
5 Correct 186 ms 78600 KB Output is correct
6 Correct 165 ms 77560 KB Output is correct
7 Correct 350 ms 121920 KB Output is correct
8 Correct 16 ms 33316 KB Output is correct
9 Correct 23 ms 34772 KB Output is correct
10 Correct 792 ms 159508 KB Output is correct
11 Correct 852 ms 161864 KB Output is correct
12 Correct 903 ms 159012 KB Output is correct
13 Correct 955 ms 161580 KB Output is correct
14 Correct 15 ms 33364 KB Output is correct
15 Correct 21 ms 34820 KB Output is correct
16 Correct 848 ms 157472 KB Output is correct
17 Correct 869 ms 158264 KB Output is correct
18 Correct 856 ms 158284 KB Output is correct
19 Correct 911 ms 158320 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33364 KB Output is correct
2 Correct 17 ms 33292 KB Output is correct
3 Correct 16 ms 33392 KB Output is correct
4 Correct 16 ms 33364 KB Output is correct
5 Correct 16 ms 33364 KB Output is correct
6 Correct 16 ms 33360 KB Output is correct
7 Correct 16 ms 33364 KB Output is correct
8 Correct 15 ms 33404 KB Output is correct
9 Correct 18 ms 33356 KB Output is correct
10 Correct 17 ms 33084 KB Output is correct
11 Correct 15 ms 33380 KB Output is correct
12 Incorrect 15 ms 33408 KB Output isn't correct
13 Halted 0 ms 0 KB -