제출 #520860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520860		danikoynov	Road Construction (JOI21_road_construction)	C++14	18 / 100	1300 ms	73288 KiB

road_construction

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 3e5 + 10;

int n, k, ridx[maxn];
ll x[maxn], y[maxn], bef[maxn], nxt[maxn];

struct element
{
    int idx;
    ll sum;
    element()
    {
        idx = 0;
        sum = 0;
    }

    element(int _idx, ll _sum)
    {
        idx = _idx;
        sum = _sum;
    }

    bool operator < (const element &e) const
    {
        return sum > e.sum;
    }
};

bool cmp(int idx1, int idx2)
{
    if (x[idx1] < x[idx2])
        return true;
    if (x[idx1] > x[idx2])
        return false;
    return y[idx1] < y[idx2];
}

struct node
{
    ll up, low;
};

node tree[maxn * 4];

node merge_node(node nd1, node nd2)
{
    node nd;
    nd.up = min(nd1.up, nd2.up);
    nd.low = min(nd1.low, nd2.low);
    return nd;
}

void clear_tree(int root, int left, int right)
{

    if (left == right)
    {
        tree[root].up = tree[root].low = 1e18;
        return;
    }

    int mid = (left + right) / 2;
    clear_tree(root * 2, left, mid);
    clear_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update(int root, int left, int right, int idx, node upd)
{
    if (left == right)
    {
        tree[root] = merge_node(tree[root], upd);
        return;
    }

    int mid = (left + right) / 2;
    if (idx <= mid)
        update(root * 2, left, mid, idx, upd);
    else
        update(root * 2 + 1, mid + 1, right, idx, upd);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left >= qleft && right <= qright)
        return tree[root];

    if (left > qright || right < qleft)
        return {(ll)1e18, (ll)1e18};

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


void solve()
{
    cin >> n >> k;
    bool y0 = true;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x[i] >> y[i];
        if (y[i] != 0)
            y0 = false;
    }

    if (n <= 1000)
    {
        vector < ll > v;
        for (int i = 1; i <= n; i ++)
            for (int j = i + 1; j <= n; j ++)
            {
                v.push_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
            }

        sort(v.begin(), v.end());
        for (int i = 0; i < k; i ++)
            cout << v[i] << endl;
    }
    else if (y0 == true)
    {
        sort(x + 1, x + n + 1);
        priority_queue < element > pq;
        for (int i = 1; i <= n; i ++)
        {
            bef[i] = i - 1;
            if (i != 1)
            {
                element e;
                e.sum = x[i] - x[i - 1];
                e.idx = i;
                pq.push(e);
            }
        }

        for (int q = 0; q < k; q ++)
        {
            element e = pq.top();
            pq.pop();
            cout << e.sum << endl;
            bef[e.idx] --;
            if (bef[e.idx] != 0)
            {
                e.sum = x[e.idx] - x[bef[e.idx]];
                pq.push(e);
            }
        }
    }
    else if (k == 1)
    {
        for (int i = 1; i <= n; i ++)
            ridx[i] = i;

        sort(ridx + 1, ridx + n + 1, cmp);
        set < ll > stx, sty;
        map < ll, int > revx, revy;
        for (int i = 1; i <= n; i ++)
        {
            stx.insert(x[i]);
            sty.insert(y[i]);
        }

        int cntx = 0;
        for (int v : stx)
            revx[v] = ++ cntx;
        int cnty = 0;
        for (int v : sty)
            revy[v] = ++ cnty;


        clear_tree(1, 1, cnty);

        ll ans = 1e18;
        for (int i = 1; i <= n; i ++)
        {
            int idx = ridx[i];
            node nd1 = query(1, 1, cnty, 1, revy[y[idx]]);
            node nd2 = query(1, 1, cnty, revy[y[idx]], cnty);

            ll sum = min(nd1.low + x[idx] + y[idx], nd2.up + x[idx] - y[idx]);
            ans = min(ans, sum);
            node nd;
            nd.low = - x[idx] - y[idx];
            nd.up = - x[idx] + y[idx];
            update(1, 1, cnty, revy[y[idx]], nd);
        }

        cout << ans << endl;

    }

}

int main()
{
    solve();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35