Submission #731281

#	Time	Username	Problem	Language	Result	Execution time	Memory
731281		danikoynov	Sky Walking (IOI19_walk)	C++14	43 / 100	233 ms	20896 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

struct skywalk
{
    int left, right;
    ll height;

    skywalk(int _left = 0, int _right = 0, ll _height = 0)
    {
        left = _left;
        right = _right;
        height = _height;
    }
}sky[maxn];

bool cmp(const skywalk &sk1, const skywalk &sk2)
{
    return sk1.height < sk2.height;
}

const ll inf = 1e18;
struct node
{
    ll down_sum, up_sum;

    node(ll _down_sum = inf, ll _up_sum = inf)
    {
        down_sum = _down_sum;
        up_sum = _up_sum;
    }
};

node merge_nodes(node lf, node rf)
{
    node nd;
    nd.down_sum = min(lf.down_sum, rf.down_sum);
    nd.up_sum = min(lf.up_sum, rf.up_sum);
    return nd;
}

node tree[4 * maxn];
int is_active[maxn];
ll dp[maxn];
void toggle(int root, int left, int right, int pos)
{
    if (left == right)
    {
        is_active[left] ^= 1;
        ///cout << root << " : " << left << " : " << right << " : " << pos << " " << is_active[left] << endl;
        if (is_active[left])
        {
            tree[root].down_sum = - sky[left].height + dp[left];
            tree[root].up_sum = sky[left].height + dp[left];
            ///cout << "activate " << left << " " << sky[left].height << endl;
        }
        else
        {
            tree[root] = node();
        }
        return;
    }

    int mid = (left + right) / 2;

    if (pos <= mid)
        toggle(root * 2, left, mid, pos);
    else
        toggle(root * 2 + 1, mid + 1, right, pos);


    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    ///cout << "here " << left << " " << right << " " << tree[root].up_sum << endl;
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
    return node();

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_nodes(query(root * 2, left, mid, qleft, qright),
                       query(root * 2 + 1, mid + 1, right, qleft, qright));
}

int n, m;
ll x[maxn], h[maxn];
vector < pair < int, int > > upd[maxn];

ll state[100][100];
bool intersects(int idx, int pos)
{
    if (sky[idx].left <= pos && sky[idx].right >= pos && sky[idx].height <= h[pos])
        return true;
    return false;
}

void relax_state(int i)
{
                for (int p1 = 0; p1 < m; p1 ++)
            {
                if (!intersects(p1, i))
                    continue;
                for (int p2 = 0; p2 < m; p2 ++)
                {
                    if (!intersects(p2, i))
                        continue;
                    state[i][p2] = min(state[i][p2], state[i][p1] + abs(sky[p1].height - sky[p2].height));
                }
            }
}
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();
    m = l.size();
    for (int i = 0; i < n; i ++)
        x[i] = X[i], h[i] = H[i];
    for (int i = 0; i < m; i ++)
    {
        sky[i] = skywalk(l[i], r[i], y[i]);
    }
    sort(sky, sky + m, cmp);

    if (n <= 50 && m <= 50)
    {
        if (s > g)
            swap(s, g);

            /**cout << "skywalk" << endl;
            for (int j = 0; j < m; j ++)
            {
                cout << j << " : " << sky[j].left << " " << sky[j].right << " " << sky[j].height << endl;
            }
            cout << "------------" << endl;*/
            for (int i = 0; i < n; i ++)
                for (int j = 0; j < m; j ++)
                state[i][j] = inf;
        for (int j = 0; j < m; j ++)
        {
            if (intersects(j, s))
                state[s][j] = sky[j].height;
        }

        for (int i = s - 1; i >= 0; i --)
        {
            for (int j = i + 1; j <= s; j ++)
            {
                for (int p = 0; p < m; p ++)
                {
                    if (intersects(p, i) && intersects(p, j))
                    {
                        state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i]));
                    }
                }
            }
            relax_state(i);
        }

        /**for (int j = 0; j < m; j ++)
            cout << state[s][j] << " ";
        cout << endl;*/

        for (int i = 0; i < n; i ++)
        {
                        for (int j = 0; j < i; j ++)
            {
                for (int p = 0; p < m; p ++)
                {
                    if (intersects(p, i) && intersects(p, j))
                    {
                        state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i]));
                    }
                }
            }


            relax_state(i);
        }

        for (int i = n - 1; i >= g; i --)
        {
            for (int j = n - 1; j > i; j --)
            {
                for (int p = 0; p < m; p ++)
                {
                    if (intersects(p, i) && intersects(p, j))
                    {
                        state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i]));
                    }
                }
            }

            relax_state(i);
        }

        ll ans = inf;
        for (int j = 0; j < m; j ++)
        {
            if (state[g][j] != inf)
                ans = min(ans, state[g][j] + sky[j].height);
        }
        if (ans == inf)
            return -1;
        return ans;
    }
    if (s != 0 || g != n - 1)
        return 0;

         for (int i = 0; i < m; i ++)
        {
            upd[sky[i].left].push_back({i, 1});
        }
        for (int i = 0; i < m; i ++)
        {

            upd[sky[i].right].push_back({i, -1});
        }



    for (pair < int, int > cur : upd[s])
    {
        dp[cur.first] = sky[cur.first].height;
        toggle(1, 0, m - 1, cur.first);
        ///cout << "here" << endl;
    }


    ///cout << tree[1].up_sum << endl;
    for (int i = 1; i < g; i ++)
    {
        for (pair < int, int > cur : upd[i])
        {

            if (cur.second == 1)
            {
                node under = node(), above = node();
                if (cur.first != 0)
                    under = query(1, 0, m - 1, 0, cur.first - 1);
                if (cur.first != m - 1)
                    above = query(1, 0, m - 1, cur.first + 1, m - 1);
            //cout << under.down_sum << " " << above.up_sum << endl;

                if (under.down_sum == inf && above.up_sum == inf)
                    dp[cur.first] = inf;
                else
                    dp[cur.first] = min(sky[cur.first].height + under.down_sum, above.up_sum - sky[cur.first].height);
                ///cout << cur.first << " :: " << dp[cur.first] << endl;
            }


            toggle(1, 0, m - 1, cur.first);
        }
    }

    node ans = tree[1];
    if (ans.up_sum == inf)
        return -1;
    return ans.up_sum + x[g] - x[s];
}

Compilation message (stderr)

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:134:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  134 |         if (s > g)
      |         ^~
walk.cpp:143:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  143 |             for (int i = 0; i < n; i ++)
      |             ^~~

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