oj.uz

Submission #520860

# Submission time Handle Problem Language Result Execution time Memory
520860 2022-01-31T08:37:43 Z danikoynov Road Construction (JOI21_road_construction) C++14
18 / 100
 1300 ms 73288 KB 
/**
 ____ ____ ____ ____ ____ ____
||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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6952 KB Output is correct
2 Correct 64 ms 6920 KB Output is correct
3 Correct 42 ms 5020 KB Output is correct
4 Correct 42 ms 4996 KB Output is correct
5 Correct 60 ms 5808 KB Output is correct
6 Correct 22 ms 4540 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 11784 KB Output is correct
2 Correct 266 ms 11656 KB Output is correct
3 Correct 52 ms 4864 KB Output is correct
4 Correct 196 ms 11428 KB Output is correct
5 Correct 190 ms 11708 KB Output is correct
6 Correct 201 ms 11720 KB Output is correct
7 Correct 197 ms 10984 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1283 ms 68636 KB Output is correct
2 Correct 1300 ms 73288 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 156 ms 13084 KB Output is correct
5 Correct 371 ms 10640 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1283 ms 68636 KB Output is correct
2 Correct 1300 ms 73288 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 156 ms 13084 KB Output is correct
5 Correct 371 ms 10640 KB Output is correct
6 Incorrect 215 ms 9232 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6952 KB Output is correct
2 Correct 64 ms 6920 KB Output is correct
3 Correct 42 ms 5020 KB Output is correct
4 Correct 42 ms 4996 KB Output is correct
5 Correct 60 ms 5808 KB Output is correct
6 Correct 22 ms 4540 KB Output is correct
7 Incorrect 77 ms 2180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6952 KB Output is correct
2 Correct 64 ms 6920 KB Output is correct
3 Correct 42 ms 5020 KB Output is correct
4 Correct 42 ms 4996 KB Output is correct
5 Correct 60 ms 5808 KB Output is correct
6 Correct 22 ms 4540 KB Output is correct
7 Correct 240 ms 11784 KB Output is correct
8 Correct 266 ms 11656 KB Output is correct
9 Correct 52 ms 4864 KB Output is correct
10 Correct 196 ms 11428 KB Output is correct
11 Correct 190 ms 11708 KB Output is correct
12 Correct 201 ms 11720 KB Output is correct
13 Correct 197 ms 10984 KB Output is correct
14 Correct 1283 ms 68636 KB Output is correct
15 Correct 1300 ms 73288 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 156 ms 13084 KB Output is correct
18 Correct 371 ms 10640 KB Output is correct
19 Incorrect 215 ms 9232 KB Output isn't correct
20 Halted 0 ms 0 KB -