Submission #448086

#	Time	Username	Problem	Language	Result	Execution time	Memory
448086		blue	Sky Walking (IOI19_walk)	C++17	0 / 100	4085 ms	35148 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];
}

bool skywalk_leq(int p, int q)
{
    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;
}

int min_skywalk(int p, int q)
{
    if(p == no_skywalk) return q;
    else if(q == no_skywalk) return p;
    return p + q - max_skywalk(p, q);
}



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 deeper_walk;
            if(l == r) deeper_walk = no_skywalk;
            else deeper_walk = max_skywalk(left->locate_lower(I, J), right->locate_lower(I, J));

            return max_skywalk(curr_walk, deeper_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_leq(w[ind + (1 << bit)], J)) continue;
                ind += (1 << bit);
            }
            ind++;

            int curr_walk = (ind >= w.size() ? no_skywalk : w[ind]);

            int deeper_walk;
            if(l == r) deeper_walk = no_skywalk;
            else deeper_walk = min_skywalk(left->locate_higher(I, J), right->locate_higher(I, J));

            return min_skywalk(curr_walk, deeper_walk);
        }
    }
};




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

void add_edge(int u, int v, long long w)
{
    cerr << "add edge " << u << ' ' << v << ' ' << w << '\n';
    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++)
    {
        cerr << "j = " << j << ' ' << L[j] << ' ' << R[j] << '\n';
        int top_walk = ST.locate_higher(R[j], j);
        if(top_walk != no_skywalk)
        {
            cerr << "t1\n";
            add_edge(j, top_walk, X[ R[top_walk] ] - X[ R[j] ] + Y[top_walk] - Y[j]);
        }

        int bottom_walk = ST.locate_lower(R[j], j);
        // cerr << "locate lower " << R[j] << ' ' << j << ' ' << r_w << '\n';
        if(bottom_walk != no_skywalk)
        {
            // cerr << "t2\n";
            add_edge(j, bottom_walk, X[ R[bottom_walk] ] - X[ R[j] ] + Y[j] - Y[bottom_walk]);
        }

        if(L[j] == 0)
        {
            add_edge(S, j, X[ R[j] ] - X[0] + Y[j]);
            cerr << "S " << j << ' ' << R[j] << ' ' << X[R[j]] << ' ' << X[0] << ' ' << Y[j] << '\n';
        }

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

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

    if(distS[G] == INF) distS[G] = -1;

    return distS[G];
}

Compilation message (stderr)

walk.cpp: In member function 'int segtree::locate_lower(int, int)':
walk.cpp:123:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                 if(ind + (1 << bit) >= w.size()) continue;
      |                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
walk.cpp: In member function 'int segtree::locate_higher(int, int)':
walk.cpp:149:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |                 if(ind + (1 << bit) >= w.size()) continue;
      |                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
walk.cpp:155:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             int curr_walk = (ind >= w.size() ? no_skywalk : w[ind]);
      |                              ~~~~^~~~~~~~~~~
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:253:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |         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