Submission #731242

#	Time	Username	Problem	Language	Result	Execution time	Memory
731242		danikoynov	Sky Walking (IOI19_walk)	C++14	0 / 100	60 ms	14576 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];
        }
        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;
vector < pair < int, int > > upd[maxn];
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 < m; i ++)
    {
        sky[i] = skywalk(l[i], r[i], y[i]);
    }
    sort(sky, sky + m, cmp);
    if (s != 0 || g != n - 1)
        return 0;

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

            upd[r[i]].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);
    }



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

            }


            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[0];
}

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