oj.uz

Submission #218184

# Submission time Handle Problem Language Result Execution time Memory
218184 2020-04-01T11:42:53 Z Alexa2001 Sky Walking (IOI19_walk) C++17
100 / 100
 819 ms 162840 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;
const int Nmax = 2e6 + 5;


///13:05

vector<int> x, h, l, r, y;
vector<int> newl, newr, newy;

vector<Pair> v[Nmax];

int nr;


void add_new(int l, int r, int y)
{
    if(l == r) return;
    newl.push_back(l); newr.push_back(r); newy.push_back(y);
}


auto cmp_buildings = [](int i, int j)
{
    return h[i] > h[j];
};

auto cmp_skywalks = [] (int i, int j)
{
    return y[i] > y[j];
};



void add_edge(int x, int y, int cost)
{
    v[x].push_back({y, cost});
    v[y].push_back({x, cost});
}

void adjust(int node)
{
    newl.clear(); newr.clear(); newy.clear();

    int m = l.size();

    vector<int> s, pref, suff;

    s.resize(m);
    pref.resize(node+1);
    suff.resize(h.size()-node);

    iota(s.begin(), s.end(), 0);
    iota(pref.begin(), pref.end(), 0);
    iota(suff.begin(), suff.end(), node);

    sort(s.begin(), s.end(), cmp_skywalks);
    sort(pref.begin(), pref.end(), cmp_buildings);
    sort(suff.begin(), suff.end(), cmp_buildings);

    int id1 = 0, id2 = 0, mx = -1, mn = h.size();

    for(auto it : s)
    {
        while(id1 < pref.size() && h[pref[id1]] >= y[it])
            mx = max(mx, pref[id1]), id1++;

        while(id2 < suff.size() && h[suff[id2]] >= y[it])
            mn = min(mn, suff[id2]), id2++;

        if(l[it] < node && node < r[it])
        {
            add_new(l[it], mx, y[it]);
            add_new(mx, mn, y[it]);
            add_new(mn, r[it], y[it]);
        }
        else add_new(l[it], r[it], y[it]);
    }

    swap(l, newl); swap(r, newr); swap(y, newy);
}



#define left_son ((node<<1))
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

class SegTree
{
    int lazy[Nmax<<2];

public:
    void propag(int node)
    {
        if(!lazy[node]) return;
        lazy[left_son] = lazy[right_son] = lazy[node];
        lazy[node] = 0;
    }

    void init()
    {
        lazy[1] = -1;
    }
    void update(int node, int st, int dr, int L, int R, int V)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] = V;
            return;
        }
        propag(node);
        if(L <= mid) update(left_son, st, mid, L, R, V);
        if(mid < R) update(right_son, mid+1, dr, L, R, V);
    }
    int query(int node, int st, int dr, int pos)
    {
        if(st == dr)
            return lazy[node];
        propag(node);
        if(pos <= mid) return query(left_son, st, mid, pos);
            else return query(right_son, mid+1, dr, pos);
    }

} aint;


void add_point(int l, int r, int id)
{
    aint.update(1, 0, h.size()-1, l, r, id);
}

int find_point(int x)
{
    return aint.query(1, 0, h.size()-1, x);
}

void find_graph(int Start, int Finish)
{
    int m = y.size(), n = h.size();
    vector<int> s(m);
    iota(s.begin(), s.end(), 0);
    sort(s.begin(), s.end(), cmp_skywalks);
    reverse(s.begin(), s.end());

    vector<Pair> points;

    aint.init();

    points.push_back({Start, m});
    points.push_back({Finish, m+1});
    y.push_back(0);
    y.push_back(0);

    add_point(Start, Start, m);
    add_point(Finish, Finish, m+1);
    m+=2;

    for(auto it : s)
    {
        points.push_back({ l[it], it });
        points.push_back({ r[it], it });

        int p1, p2;
        p1 = find_point(l[it]);
        p2 = find_point(r[it]);

        if(p1 != -1)
            points.push_back({ l[it], p1 });

        if(p2 != -1)
            points.push_back({ r[it], p2 });

        add_point(l[it], r[it], it);
    }

    vector<vector<Pair>> vx(n), vy(m);

    nr = 0;
    for(auto p : points)
    {
        ++nr;
        vx[p.first].push_back({y[p.second], nr});
        vy[p.second].push_back({x[p.first], nr});
    }

    int i, j;
    for(i=0; i<n; ++i)
    {
        sort(vx[i].begin(), vx[i].end());
        for(j=0; j+1<vx[i].size(); ++j)
            add_edge(vx[i][j].second, vx[i][j+1].second, vx[i][j+1].first - vx[i][j].first);
    }

    for(i=0; i<m; ++i)
    {
        sort(vy[i].begin(), vy[i].end());
        for(j=0; j+1<vy[i].size(); ++j)
            add_edge(vy[i][j].second, vy[i][j+1].second, vy[i][j+1].first - vy[i][j].first);
    }
}

ll dijkstra(int S, int F)
{
    priority_queue< pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>> > heap;
    vector<ll> d(nr+1, LLONG_MAX);

    d[S] = 0;
    heap.push({0, S});

    while(heap.size())
    {
        int node; ll dist;
        tie(dist, node) = heap.top();
        heap.pop();

        if(dist != d[node]) continue;
        if(node == F) return d[F];

        for(auto it : v[node])
            if(d[it.first] > d[node] + it.second)
            {
                d[it.first] = d[node] + it.second;
                heap.push({d[it.first], it.first});
            }
    }
    return -1;
}

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int Start, int Finish)
{
    x = X; h = H; l = L; r = R; y = Y;

    adjust(Start);
    adjust(Finish);

    find_graph(Start, Finish);
    return dijkstra(1, 2);
}

Compilation message

walk.cpp: In function 'void adjust(int)':
walk.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(id1 < pref.size() && h[pref[id1]] >= y[it])
               ~~~~^~~~~~~~~~~~~
walk.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(id2 < suff.size() && h[suff[id2]] >= y[it])
               ~~~~^~~~~~~~~~~~~
walk.cpp: In function 'void find_graph(int, int)':
walk.cpp:196:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j+1<vx[i].size(); ++j)
                  ~~~^~~~~~~~~~~~~
walk.cpp:203:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j+1<vy[i].size(); ++j)
                  ~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47232 KB Output is correct
2 Correct 30 ms 47232 KB Output is correct
3 Correct 30 ms 47360 KB Output is correct
4 Correct 33 ms 47280 KB Output is correct
5 Correct 31 ms 47360 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 31 ms 47352 KB Output is correct
8 Correct 30 ms 47360 KB Output is correct
9 Correct 30 ms 47232 KB Output is correct
10 Correct 29 ms 47360 KB Output is correct
11 Correct 29 ms 47360 KB Output is correct
12 Correct 30 ms 47232 KB Output is correct
13 Correct 30 ms 47256 KB Output is correct
14 Correct 30 ms 47360 KB Output is correct
15 Correct 30 ms 47336 KB Output is correct
16 Correct 30 ms 47232 KB Output is correct
17 Correct 29 ms 47360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47224 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct
3 Correct 351 ms 89884 KB Output is correct
4 Correct 533 ms 93064 KB Output is correct
5 Correct 304 ms 82512 KB Output is correct
6 Correct 309 ms 82776 KB Output is correct
7 Correct 315 ms 82760 KB Output is correct
8 Correct 374 ms 89912 KB Output is correct
9 Correct 420 ms 91820 KB Output is correct
10 Correct 526 ms 93288 KB Output is correct
11 Correct 396 ms 89908 KB Output is correct
12 Correct 424 ms 86480 KB Output is correct
13 Correct 540 ms 93240 KB Output is correct
14 Correct 271 ms 82952 KB Output is correct
15 Correct 331 ms 86288 KB Output is correct
16 Correct 361 ms 88636 KB Output is correct
17 Correct 346 ms 86684 KB Output is correct
18 Correct 283 ms 89388 KB Output is correct
19 Correct 40 ms 49404 KB Output is correct
20 Correct 138 ms 66196 KB Output is correct
21 Correct 376 ms 88828 KB Output is correct
22 Correct 344 ms 86580 KB Output is correct
23 Correct 307 ms 88372 KB Output is correct
24 Correct 354 ms 87536 KB Output is correct
25 Correct 378 ms 87476 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 67944 KB Output is correct
2 Correct 349 ms 88772 KB Output is correct
3 Correct 468 ms 90316 KB Output is correct
4 Correct 520 ms 94260 KB Output is correct
5 Correct 612 ms 94140 KB Output is correct
6 Correct 509 ms 94004 KB Output is correct
7 Correct 299 ms 74452 KB Output is correct
8 Correct 396 ms 86264 KB Output is correct
9 Correct 517 ms 94260 KB Output is correct
10 Correct 291 ms 87984 KB Output is correct
11 Correct 56 ms 50356 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 67944 KB Output is correct
2 Correct 349 ms 88772 KB Output is correct
3 Correct 468 ms 90316 KB Output is correct
4 Correct 520 ms 94260 KB Output is correct
5 Correct 612 ms 94140 KB Output is correct
6 Correct 509 ms 94004 KB Output is correct
7 Correct 299 ms 74452 KB Output is correct
8 Correct 396 ms 86264 KB Output is correct
9 Correct 517 ms 94260 KB Output is correct
10 Correct 291 ms 87984 KB Output is correct
11 Correct 56 ms 50356 KB Output is correct
12 Correct 452 ms 90056 KB Output is correct
13 Correct 449 ms 94152 KB Output is correct
14 Correct 559 ms 93996 KB Output is correct
15 Correct 444 ms 87752 KB Output is correct
16 Correct 554 ms 95032 KB Output is correct
17 Correct 535 ms 94772 KB Output is correct
18 Correct 445 ms 87604 KB Output is correct
19 Correct 529 ms 95024 KB Output is correct
20 Correct 291 ms 74076 KB Output is correct
21 Correct 89 ms 53616 KB Output is correct
22 Correct 330 ms 87916 KB Output is correct
23 Correct 348 ms 89528 KB Output is correct
24 Correct 330 ms 86680 KB Output is correct
25 Correct 338 ms 86900 KB Output is correct
26 Correct 284 ms 82720 KB Output is correct
27 Correct 579 ms 94380 KB Output is correct
28 Correct 423 ms 94516 KB Output is correct
29 Correct 566 ms 94032 KB Output is correct
30 Correct 298 ms 74452 KB Output is correct
31 Correct 478 ms 94256 KB Output is correct
32 Correct 365 ms 88076 KB Output is correct
33 Correct 299 ms 87220 KB Output is correct
34 Correct 307 ms 88372 KB Output is correct
35 Correct 363 ms 88904 KB Output is correct
36 Correct 394 ms 88320 KB Output is correct
37 Correct 375 ms 89112 KB Output is correct
38 Correct 323 ms 86448 KB Output is correct
39 Correct 315 ms 88520 KB Output is correct
40 Correct 361 ms 87396 KB Output is correct
41 Correct 385 ms 87764 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47232 KB Output is correct
2 Correct 30 ms 47232 KB Output is correct
3 Correct 30 ms 47360 KB Output is correct
4 Correct 33 ms 47280 KB Output is correct
5 Correct 31 ms 47360 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 31 ms 47352 KB Output is correct
8 Correct 30 ms 47360 KB Output is correct
9 Correct 30 ms 47232 KB Output is correct
10 Correct 29 ms 47360 KB Output is correct
11 Correct 29 ms 47360 KB Output is correct
12 Correct 30 ms 47232 KB Output is correct
13 Correct 30 ms 47256 KB Output is correct
14 Correct 30 ms 47360 KB Output is correct
15 Correct 30 ms 47336 KB Output is correct
16 Correct 30 ms 47232 KB Output is correct
17 Correct 29 ms 47360 KB Output is correct
18 Correct 32 ms 47224 KB Output is correct
19 Correct 29 ms 47360 KB Output is correct
20 Correct 351 ms 89884 KB Output is correct
21 Correct 533 ms 93064 KB Output is correct
22 Correct 304 ms 82512 KB Output is correct
23 Correct 309 ms 82776 KB Output is correct
24 Correct 315 ms 82760 KB Output is correct
25 Correct 374 ms 89912 KB Output is correct
26 Correct 420 ms 91820 KB Output is correct
27 Correct 526 ms 93288 KB Output is correct
28 Correct 396 ms 89908 KB Output is correct
29 Correct 424 ms 86480 KB Output is correct
30 Correct 540 ms 93240 KB Output is correct
31 Correct 271 ms 82952 KB Output is correct
32 Correct 331 ms 86288 KB Output is correct
33 Correct 361 ms 88636 KB Output is correct
34 Correct 346 ms 86684 KB Output is correct
35 Correct 283 ms 89388 KB Output is correct
36 Correct 40 ms 49404 KB Output is correct
37 Correct 138 ms 66196 KB Output is correct
38 Correct 376 ms 88828 KB Output is correct
39 Correct 344 ms 86580 KB Output is correct
40 Correct 307 ms 88372 KB Output is correct
41 Correct 354 ms 87536 KB Output is correct
42 Correct 378 ms 87476 KB Output is correct
43 Correct 192 ms 67944 KB Output is correct
44 Correct 349 ms 88772 KB Output is correct
45 Correct 468 ms 90316 KB Output is correct
46 Correct 520 ms 94260 KB Output is correct
47 Correct 612 ms 94140 KB Output is correct
48 Correct 509 ms 94004 KB Output is correct
49 Correct 299 ms 74452 KB Output is correct
50 Correct 396 ms 86264 KB Output is correct
51 Correct 517 ms 94260 KB Output is correct
52 Correct 291 ms 87984 KB Output is correct
53 Correct 56 ms 50356 KB Output is correct
54 Correct 452 ms 90056 KB Output is correct
55 Correct 449 ms 94152 KB Output is correct
56 Correct 559 ms 93996 KB Output is correct
57 Correct 444 ms 87752 KB Output is correct
58 Correct 554 ms 95032 KB Output is correct
59 Correct 535 ms 94772 KB Output is correct
60 Correct 445 ms 87604 KB Output is correct
61 Correct 529 ms 95024 KB Output is correct
62 Correct 291 ms 74076 KB Output is correct
63 Correct 89 ms 53616 KB Output is correct
64 Correct 330 ms 87916 KB Output is correct
65 Correct 348 ms 89528 KB Output is correct
66 Correct 330 ms 86680 KB Output is correct
67 Correct 338 ms 86900 KB Output is correct
68 Correct 284 ms 82720 KB Output is correct
69 Correct 579 ms 94380 KB Output is correct
70 Correct 423 ms 94516 KB Output is correct
71 Correct 566 ms 94032 KB Output is correct
72 Correct 298 ms 74452 KB Output is correct
73 Correct 478 ms 94256 KB Output is correct
74 Correct 365 ms 88076 KB Output is correct
75 Correct 299 ms 87220 KB Output is correct
76 Correct 307 ms 88372 KB Output is correct
77 Correct 363 ms 88904 KB Output is correct
78 Correct 394 ms 88320 KB Output is correct
79 Correct 375 ms 89112 KB Output is correct
80 Correct 323 ms 86448 KB Output is correct
81 Correct 315 ms 88520 KB Output is correct
82 Correct 361 ms 87396 KB Output is correct
83 Correct 385 ms 87764 KB Output is correct
84 Correct 142 ms 63440 KB Output is correct
85 Correct 445 ms 94872 KB Output is correct
86 Correct 669 ms 122748 KB Output is correct
87 Correct 91 ms 56796 KB Output is correct
88 Correct 110 ms 57712 KB Output is correct
89 Correct 96 ms 56636 KB Output is correct
90 Correct 56 ms 51952 KB Output is correct
91 Correct 30 ms 47488 KB Output is correct
92 Correct 47 ms 49656 KB Output is correct
93 Correct 199 ms 68316 KB Output is correct
94 Correct 92 ms 54080 KB Output is correct
95 Correct 356 ms 89540 KB Output is correct
96 Correct 342 ms 89904 KB Output is correct
97 Correct 320 ms 86596 KB Output is correct
98 Correct 338 ms 86640 KB Output is correct
99 Correct 819 ms 162840 KB Output is correct
100 Correct 517 ms 98852 KB Output is correct
101 Correct 585 ms 121772 KB Output is correct
102 Correct 265 ms 77620 KB Output is correct
103 Correct 354 ms 91024 KB Output is correct
104 Correct 320 ms 90168 KB Output is correct
105 Correct 319 ms 91308 KB Output is correct
106 Correct 315 ms 90676 KB Output is correct
107 Correct 303 ms 90420 KB Output is correct
108 Correct 59 ms 51480 KB Output is correct
109 Correct 467 ms 88864 KB Output is correct
110 Correct 431 ms 99204 KB Output is correct
111 Correct 408 ms 100628 KB Output is correct
112 Correct 355 ms 92076 KB Output is correct
113 Correct 386 ms 91608 KB Output is correct