Submission #448046

#	Time	Username	Problem	Language	Result	Execution time	Memory
448046		blue	Sky Walking (IOI19_walk)	C++17	0 / 100	175 ms	15052 KiB

walk

#include "walk.h"
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 100'000;
const int maxM = 100'000;
const int lg = 19;
const long long INF = 1'000'000'000'000'000'000LL;

int N;
vector<int> X;
vector<int> H;

int M;
vector<int> L;
vector<int> R;
vector<int> Y;

const int S = maxM;
const int G = maxM + 1;
const int no_skywalk = -1;






bool skywalk_comp(int p, int q) //compare skywalks by height
{
    if(p == no_skywalk) return 1; //-1 -> height = -INF
    else if(q == no_skywalk) return 0;
    else if(Y[p] == Y[q]) return p < q;
    else return Y[p] < Y[q];
}

int max_skywalk(int p, int q)
{
    if(skywalk_comp(p, q)) return q;
    else return p;
}



struct segtree
{
    int l;
    int r;
    vector<int> w; //skywalks sorted by height

    segtree* left = NULL;
    segtree* right = NULL;


    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;

        if(l == r) return;

        int m = (l+r)/2;

        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void add_skywalk(int i) //over L[i] to R[i];
    {
        if(R[i] < l || r < L[i]) return;
        else if(L[i] <= l && r <= R[i])
        {
            w.push_back(i);
        }
        else
        {
            left->add_skywalk(i);
            right->add_skywalk(i);
        }
    }

    void sort_skywalks()
    {
        sort(w.begin(), w.end(), skywalk_comp);

        if(l != r)
        {
            left->sort_skywalks();
            right->sort_skywalks();
        }
    }

    int locate_lower(int I, int J) //building i, skywalk j
    {
        //if(I < L[J] || R[J] < I) return -1; //guaranteed;
        if(I < l || r < I) return no_skywalk;
        else
        {
            int ind = -1;
            for(int bit = lg; bit >= 0; bit--)
            {
                if(ind + (1 << bit) >= w.size()) continue;
                if(!skywalk_comp(w[ind + (1 << bit)], J)) continue;
                ind += (1 << bit);
            }

            if(ind != -1 && w[ind] == I) ind--;

            int curr_walk = (ind == -1) ? no_skywalk : w[ind];

            int lower_walk;
            if(l == r) lower_walk = no_skywalk;
            else lower_walk = max_skywalk(left->locate_lower(I, J), right->locate_lower(I, J));

            return max_skywalk(curr_walk, lower_walk);
        }
    }

    // int locate_higher(int I, int J) //building i, skywalk j
    // {
    //     //if(I < L[J] || R[J] < I) return -1; //guaranteed;
    //     if(I < l || r < I) return no_skywalk;
    //     else
    //     {
    //         int ind = -1;
    //         for(int bit = lg; bit >= 0; bit--)
    //         {
    //             if(ind + (1 << bit) >= w.size()) continue;
    //             if(!skywalk_comp(w[ind + (1 << bit)], J)) continue;
    //             ind += (1 << bit);
    //         }
    //     }
    // }
};




vector<int> edge[maxM + 3];
vector<long long> dist[maxM + 3];

void add_edge(int u, int v, long long w)
{
    edge[u].push_back(v);
    dist[u].push_back(w);
}

vector<long long> distS(maxM + 3, INF);

struct pos
{
    int i;
};

bool operator < (pos A, pos B)
{
    if(distS[A.i] == distS[B.i]) return A.i < B.i;
    return distS[A.i] < distS[B.i];
}



long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
    N = x.size();
    X = x;
    H = h;

    M = l.size();
    L = l;
    R = r;
    Y = y;

    //source = 0, destination = n-1
    segtree ST(0, N-1);
    for(int j = 0; j < M; j++)
        ST.add_skywalk(j);

    ST.sort_skywalks();


    for(int j = 0; j < M; j++)
    {
        int l_w = ST.locate_lower(L[j], j);
        if(l_w != no_skywalk)
        {
            add_edge(l_w, j, X[ R[j] ] - X[ L[j] ] + Y[j] - Y[l_w]);
        }

        int r_w = ST.locate_lower(R[j], j);
        if(r_w != no_skywalk)
        {
            add_edge(j, r_w, X[ R[r_w] ] - X[ R[j] ] + Y[j] - Y[r_w]);
        }

        if(L[j] == 0)
            add_edge(S, j, X[ R[j] ] + Y[j]);

        if(R[j] == N-1)
            add_edge(j, G, Y[j]);
    }


    distS[S] = 0;
    set<pos> tbv;
    for(int j = 0; j < M; j++) tbv.insert(pos{j});
    tbv.insert(pos{S});
    tbv.insert(pos{G});

    while(!tbv.empty())
    {
        int u = tbv.begin()->i;
        tbv.erase(tbv.begin());

        for(int e = 0; e < edge[u].size(); e++)
        {
            int v = edge[u][e];
            long long wt = dist[u][e];

            if(distS[v] > distS[u] + wt)
            {
                tbv.erase(pos{v});
                // cerr << u << ' ' << v << ' ' << distS[u] + wt << '\n';
                distS[v] = distS[u] + wt;
                tbv.insert(pos{v});
            }
        }
    }

    // for(int j = 0; j < M; j++) cerr << j << ' ' << distS[j] << '\n';
    // cerr << "S " << distS[S] << '\n';
    // cerr << "G " << distS[G] << '\n';

    return distS[G];
}

Compilation message (stderr)

walk.cpp: In member function 'int segtree::locate_lower(int, int)':
walk.cpp:108:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 if(ind + (1 << bit) >= w.size()) continue;
      |                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:221:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |         for(int e = 0; e < edge[u].size(); e++)
      |                        ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43