Submission #218184

#	Time	Username	Problem	Language	Result	Execution time	Memory
218184		Alexa2001	Sky Walking (IOI19_walk)	C++17	100 / 100	819 ms	162840 KiB

walk

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43