oj.uz

Submission #1096663

# Submission time Handle Problem Language Result Execution time Memory
1096663 2024-10-05T00:12:06 Z azberjibiou Sky Walking (IOI19_walk) C++17
100 / 100
 1190 ms 135828 KB 
#include "walk.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=100050;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct line{
    int l, r, h;
};
int N, M;
int pos[mxN], A[mxN];
line B[mxN];
int st, en;
int sidx, eidx;
map <pii, int> vtx;
pii V[12*mxN];
int vidx;
vector <pll> adj[12*mxN];
/*
void input(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> pos[i];
    for(int i=0;i<N;i++) cin >> A[i];
    for(int i=1;i<=M;i++) cin >> B[i].l >> B[i].r >> B[i].h;
    for(int i=1;i<=M;i++) B[i].l=pos[B[i].l], B[i].r=pos[B[i].r];
    cin >> st >> en;
}
*/
void no_endpoint(){
    vector <line> v;
    for(int i=1;i<=M;i++) v.push_back(B[i]);
    sort(all(v), [](line a, line b){return a.h!=b.h ? a.h<b.h : a.l<b.l;});
    vector <line> res;
    line prev={-1, -1, -1};
    for(line x : v){
        if(x.h!=prev.h || prev.r<x.l){
            if(prev.h!=-1) res.push_back(prev);
            prev=x;
        }
        else prev.r=x.r;
    }
    if(prev.h!=-1) res.push_back(prev);
    M=res.size();
    for(int i=1;i<=M;i++) B[i]=res[i-1];
}
void init(vector <int> x, vector <int> h, vector <int> l, vector <int> r, vector <int> y, int s, int g){
    N=x.size(); M=l.size();
    for(int i=0;i<N;i++) pos[i]=x[i];
    for(int i=0;i<N;i++) A[i]=h[i];
    for(int i=1;i<=M;i++) B[i].l=l[i-1], B[i].r=r[i-1], B[i].h=y[i-1];
  	for(int i=1;i<=M;i++) B[i].l=pos[B[i].l], B[i].r=pos[B[i].r];
    no_endpoint();
    st=s, en=g;
}
void add_edge(int a, int b, int c){
    adj[a].emplace_back(b, c);
    adj[b].emplace_back(a, c);
}
void add(vector <int> &v1, int val, pii rng){
    if(val==-1) return;
    if(val>rng.se || val<rng.fi) return;
    v1.push_back(val);
}
int lb(set <int> &s, int val){
    auto it=s.lower_bound(val);
    return (it==s.end() ? -1 : *it);
}
int rb(set <int> &s, int val){
    auto it=s.lower_bound(val+1);
    if(it==s.begin()) return -1;
    it--;
    return *it;
}
void make_graph(){
    set <int> xcr;
    set <pii> fall; // x값, 끝점 index
    vector <pii> hv;
    for(int i=0;i<N;i++) hv.emplace_back(A[i], i);
    sort(all(hv));
    vector <int> turn;
    for(int i=1;i<=M;i++) turn.push_back(i);
    sort(all(turn), [&](int a, int b){return B[a].h>B[b].h;});
    for(int now : turn){
        auto [nl, nr, nh]=B[now];
        while(hv.size() && hv.back().fi>=nh){
            int idx=hv.back().se;
            hv.pop_back();
            xcr.insert(pos[idx]);
        }
        vector <int> cr;
        vector <pii> up; // x값, 끝점 index
        vector <int> down;
        //get up edges
        while(true){
            if(fall.empty()) break;
            auto it=fall.lower_bound(pii(nl, 0));
            if(it==fall.end() || it->fi>nr) break;
            up.push_back(*it);
            fall.erase(it);
        }
        // add down vertices
        add(down, lb(xcr, nl), pii(nl, nr));
        if(nl<=pos[st] && pos[st]<=nr){
            add(down, lb(xcr, pos[st]), pii(nl, nr));
            add(down, rb(xcr, pos[st]), pii(nl, nr));
        }
        if(nl<=pos[en] && pos[en]<=nr){
            add(down, lb(xcr, pos[en]), pii(nl, nr));
            add(down, rb(xcr, pos[en]), pii(nl, nr));
        }
        add(down, rb(xcr, nr), pii(nl, nr));
        sort(all(down));
        down.erase(unique(all(down)), down.end());
        /*
        printf("nl, nr, nh=%d %d %d\n", nl, nr, nh);
        for(int x : down) printf("%d ", x);
        printf("\n");
        printf("xcr: ");
        for(int x : xcr) printf("%d ", x);
        printf("\n");
        */
        //make vertices
        for(int x : down) cr.push_back(x);
        for(auto [x, idx] : up) cr.push_back(x);
        sort(all(cr));
        cr.erase(unique(all(cr)), cr.end());
        for(int i=0;i<cr.size();i++){
            int x=cr[i];
            if(vtx.count(pii(x, nh))==0){
              	V[vidx]=pii(x, nh);
            	vtx[pii(x, nh)]=vidx++;
            }
            //also make horizontal edges
            if(i-1>=0) add_edge(vtx[pii(x, nh)], vtx[pii(cr[i-1], nh)], cr[i]-cr[i-1]);
        }
        //make up edges
        for(auto [x, num1] : up){
            int num2=vtx[pii(x, nh)];
            add_edge(num1, num2, V[num1].se-nh);
        }
        //make down edges
        for(int x : down){
            fall.insert(pii(x, vtx[pii(x, nh)]));
        }
    }
    //make st and en
    V[vidx]=pii(pos[st], 0);
    vtx[pii(pos[st], 0)]=vidx;
    sidx=vidx++;
    V[vidx]=pii(pos[en], 0);
    vtx[pii(pos[en], 0)]=vidx;
    eidx=vidx++;
    //adding edge for st and en
    auto itst=fall.lower_bound(pii(pos[st], 0));
    if(itst!=fall.end() && itst->fi==pos[st]){
        int nxt=itst->se;
        add_edge(sidx, nxt, V[nxt].se);
    }
    auto iten=fall.lower_bound(pii(pos[en], 0));
    if(iten!=fall.end() && iten->fi==pos[en]){
        int nxt=iten->se;
        add_edge(eidx, nxt, V[nxt].se);
    }
    /*
    for(int i=0;i<vidx;i++) printf("V[%d]=%d %d\n", i, V[i].fi, V[i].se);
    for(int i=0;i<vidx;i++){
        printf("i=%d: ", i);
        for(auto [x, y] : adj[i]) printf("(%lld %lld) ", x, y);
        printf("\n");
    }
    */
}
ll dist[12*mxN];
ll ans;
void dijkstra(){
    for(int i=0;i<vidx;i++) dist[i]=-1;
    priority_queue <pll> pq;
    pq.emplace(0, sidx);
    while(pq.size()){
        auto [x, now]=pq.top();
        pq.pop();
        if(dist[now]!=-1) continue;
        dist[now]=-x;
        for(auto [nxt, val] : adj[now]) pq.emplace(x-val, nxt);
    }
    //for(int i=0;i<vidx;i++) printf("dist[%d]=%lld\n", i, dist[i]);
    ans=dist[eidx];
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	init(x, h, l, r, y, s, g);
    make_graph();
    dijkstra();
    return ans;
}
/*
int main(){
    gibon
    input();
    make_graph();
    dijkstra();
    cout << ans;
}
*/
/*
7 7
0 3 5 7 10 12 14
8 7 9 7 6 6 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

Compilation message

walk.cpp: In function 'void make_graph()':
walk.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for(int i=0;i<cr.size();i++){
      |                     ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 11 ms 28460 KB Output is correct
3 Correct 15 ms 28504 KB Output is correct
4 Correct 11 ms 28504 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 12 ms 28508 KB Output is correct
8 Correct 11 ms 28500 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 12 ms 28508 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 11 ms 28516 KB Output is correct
13 Correct 11 ms 28444 KB Output is correct
14 Correct 11 ms 28504 KB Output is correct
15 Correct 12 ms 28504 KB Output is correct
16 Correct 12 ms 28508 KB Output is correct
17 Correct 12 ms 28504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 605 ms 80992 KB Output is correct
4 Correct 671 ms 88640 KB Output is correct
5 Correct 391 ms 75216 KB Output is correct
6 Correct 427 ms 73132 KB Output is correct
7 Correct 411 ms 75444 KB Output is correct
8 Correct 588 ms 83352 KB Output is correct
9 Correct 506 ms 84492 KB Output is correct
10 Correct 629 ms 89096 KB Output is correct
11 Correct 536 ms 76220 KB Output is correct
12 Correct 454 ms 71320 KB Output is correct
13 Correct 660 ms 91036 KB Output is correct
14 Correct 310 ms 67788 KB Output is correct
15 Correct 336 ms 76572 KB Output is correct
16 Correct 267 ms 75704 KB Output is correct
17 Correct 284 ms 73400 KB Output is correct
18 Correct 272 ms 72212 KB Output is correct
19 Correct 22 ms 30628 KB Output is correct
20 Correct 167 ms 50420 KB Output is correct
21 Correct 236 ms 72928 KB Output is correct
22 Correct 244 ms 76432 KB Output is correct
23 Correct 401 ms 81164 KB Output is correct
24 Correct 245 ms 75596 KB Output is correct
25 Correct 273 ms 73072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 32136 KB Output is correct
2 Correct 609 ms 87676 KB Output is correct
3 Correct 658 ms 89476 KB Output is correct
4 Correct 740 ms 96792 KB Output is correct
5 Correct 741 ms 96936 KB Output is correct
6 Correct 663 ms 93840 KB Output is correct
7 Correct 326 ms 66848 KB Output is correct
8 Correct 404 ms 71344 KB Output is correct
9 Correct 578 ms 90808 KB Output is correct
10 Correct 248 ms 72376 KB Output is correct
11 Correct 24 ms 32460 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 32136 KB Output is correct
2 Correct 609 ms 87676 KB Output is correct
3 Correct 658 ms 89476 KB Output is correct
4 Correct 740 ms 96792 KB Output is correct
5 Correct 741 ms 96936 KB Output is correct
6 Correct 663 ms 93840 KB Output is correct
7 Correct 326 ms 66848 KB Output is correct
8 Correct 404 ms 71344 KB Output is correct
9 Correct 578 ms 90808 KB Output is correct
10 Correct 248 ms 72376 KB Output is correct
11 Correct 24 ms 32460 KB Output is correct
12 Correct 727 ms 89440 KB Output is correct
13 Correct 603 ms 96748 KB Output is correct
14 Correct 754 ms 99184 KB Output is correct
15 Correct 463 ms 88520 KB Output is correct
16 Correct 527 ms 91248 KB Output is correct
17 Correct 551 ms 99016 KB Output is correct
18 Correct 441 ms 88636 KB Output is correct
19 Correct 525 ms 90572 KB Output is correct
20 Correct 374 ms 65348 KB Output is correct
21 Correct 68 ms 36848 KB Output is correct
22 Correct 468 ms 84940 KB Output is correct
23 Correct 443 ms 83488 KB Output is correct
24 Correct 365 ms 72920 KB Output is correct
25 Correct 416 ms 79504 KB Output is correct
26 Correct 288 ms 67788 KB Output is correct
27 Correct 745 ms 98340 KB Output is correct
28 Correct 616 ms 96208 KB Output is correct
29 Correct 695 ms 95924 KB Output is correct
30 Correct 360 ms 66844 KB Output is correct
31 Correct 660 ms 92632 KB Output is correct
32 Correct 239 ms 70892 KB Output is correct
33 Correct 249 ms 72816 KB Output is correct
34 Correct 328 ms 75008 KB Output is correct
35 Correct 319 ms 77720 KB Output is correct
36 Correct 328 ms 72708 KB Output is correct
37 Correct 224 ms 70148 KB Output is correct
38 Correct 258 ms 73320 KB Output is correct
39 Correct 382 ms 78268 KB Output is correct
40 Correct 250 ms 72612 KB Output is correct
41 Correct 259 ms 70252 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 11 ms 28460 KB Output is correct
3 Correct 15 ms 28504 KB Output is correct
4 Correct 11 ms 28504 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 12 ms 28508 KB Output is correct
8 Correct 11 ms 28500 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 12 ms 28508 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 11 ms 28516 KB Output is correct
13 Correct 11 ms 28444 KB Output is correct
14 Correct 11 ms 28504 KB Output is correct
15 Correct 12 ms 28504 KB Output is correct
16 Correct 12 ms 28508 KB Output is correct
17 Correct 12 ms 28504 KB Output is correct
18 Correct 12 ms 28508 KB Output is correct
19 Correct 11 ms 28508 KB Output is correct
20 Correct 605 ms 80992 KB Output is correct
21 Correct 671 ms 88640 KB Output is correct
22 Correct 391 ms 75216 KB Output is correct
23 Correct 427 ms 73132 KB Output is correct
24 Correct 411 ms 75444 KB Output is correct
25 Correct 588 ms 83352 KB Output is correct
26 Correct 506 ms 84492 KB Output is correct
27 Correct 629 ms 89096 KB Output is correct
28 Correct 536 ms 76220 KB Output is correct
29 Correct 454 ms 71320 KB Output is correct
30 Correct 660 ms 91036 KB Output is correct
31 Correct 310 ms 67788 KB Output is correct
32 Correct 336 ms 76572 KB Output is correct
33 Correct 267 ms 75704 KB Output is correct
34 Correct 284 ms 73400 KB Output is correct
35 Correct 272 ms 72212 KB Output is correct
36 Correct 22 ms 30628 KB Output is correct
37 Correct 167 ms 50420 KB Output is correct
38 Correct 236 ms 72928 KB Output is correct
39 Correct 244 ms 76432 KB Output is correct
40 Correct 401 ms 81164 KB Output is correct
41 Correct 245 ms 75596 KB Output is correct
42 Correct 273 ms 73072 KB Output is correct
43 Correct 26 ms 32136 KB Output is correct
44 Correct 609 ms 87676 KB Output is correct
45 Correct 658 ms 89476 KB Output is correct
46 Correct 740 ms 96792 KB Output is correct
47 Correct 741 ms 96936 KB Output is correct
48 Correct 663 ms 93840 KB Output is correct
49 Correct 326 ms 66848 KB Output is correct
50 Correct 404 ms 71344 KB Output is correct
51 Correct 578 ms 90808 KB Output is correct
52 Correct 248 ms 72376 KB Output is correct
53 Correct 24 ms 32460 KB Output is correct
54 Correct 727 ms 89440 KB Output is correct
55 Correct 603 ms 96748 KB Output is correct
56 Correct 754 ms 99184 KB Output is correct
57 Correct 463 ms 88520 KB Output is correct
58 Correct 527 ms 91248 KB Output is correct
59 Correct 551 ms 99016 KB Output is correct
60 Correct 441 ms 88636 KB Output is correct
61 Correct 525 ms 90572 KB Output is correct
62 Correct 374 ms 65348 KB Output is correct
63 Correct 68 ms 36848 KB Output is correct
64 Correct 468 ms 84940 KB Output is correct
65 Correct 443 ms 83488 KB Output is correct
66 Correct 365 ms 72920 KB Output is correct
67 Correct 416 ms 79504 KB Output is correct
68 Correct 288 ms 67788 KB Output is correct
69 Correct 745 ms 98340 KB Output is correct
70 Correct 616 ms 96208 KB Output is correct
71 Correct 695 ms 95924 KB Output is correct
72 Correct 360 ms 66844 KB Output is correct
73 Correct 660 ms 92632 KB Output is correct
74 Correct 239 ms 70892 KB Output is correct
75 Correct 249 ms 72816 KB Output is correct
76 Correct 328 ms 75008 KB Output is correct
77 Correct 319 ms 77720 KB Output is correct
78 Correct 328 ms 72708 KB Output is correct
79 Correct 224 ms 70148 KB Output is correct
80 Correct 258 ms 73320 KB Output is correct
81 Correct 382 ms 78268 KB Output is correct
82 Correct 250 ms 72612 KB Output is correct
83 Correct 259 ms 70252 KB Output is correct
84 Correct 25 ms 32088 KB Output is correct
85 Correct 726 ms 93640 KB Output is correct
86 Correct 951 ms 118824 KB Output is correct
87 Correct 69 ms 43220 KB Output is correct
88 Correct 91 ms 43884 KB Output is correct
89 Correct 80 ms 43244 KB Output is correct
90 Correct 18 ms 30200 KB Output is correct
91 Correct 12 ms 28820 KB Output is correct
92 Correct 30 ms 31592 KB Output is correct
93 Correct 268 ms 58768 KB Output is correct
94 Correct 72 ms 38972 KB Output is correct
95 Correct 502 ms 91392 KB Output is correct
96 Correct 458 ms 87776 KB Output is correct
97 Correct 363 ms 77044 KB Output is correct
98 Correct 436 ms 83220 KB Output is correct
99 Correct 1190 ms 135828 KB Output is correct
100 Correct 750 ms 101248 KB Output is correct
101 Correct 854 ms 110444 KB Output is correct
102 Correct 385 ms 69920 KB Output is correct
103 Correct 252 ms 73932 KB Output is correct
104 Correct 254 ms 75892 KB Output is correct
105 Correct 315 ms 77936 KB Output is correct
106 Correct 292 ms 76216 KB Output is correct
107 Correct 359 ms 79216 KB Output is correct
108 Correct 49 ms 34156 KB Output is correct
109 Correct 610 ms 88396 KB Output is correct
110 Correct 675 ms 100972 KB Output is correct
111 Correct 689 ms 100880 KB Output is correct
112 Correct 350 ms 79596 KB Output is correct
113 Correct 369 ms 77836 KB Output is correct