Submission #1258473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258473		chikien2009	Road Construction (JOI21_road_construction)	C++20	100 / 100	3754 ms	25916 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

long long n, k, lb, rb, mid, res;
array<long long, 3> p[250000];
vector<long long> g;

struct SEGMENT_TREE
{
    long long tree[1000000], num;
    vector<long long> con;
    inline void Init()
    {
        fill_n(tree, 1e6, 1e18);
    }
    inline void Set(long long ind, long long l, long long r, long long x, long long v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind] = v;
            return;
        }
        long long m = (l + r) >> 1;
        Set(ind << 1, l, m, x, v);
        Set(ind << 1 | 1, m + 1, r, x, v);
        tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
    }
    inline void Get(long long ind, long long l, long long r, long long x, long long y, long long v, long long dist, long long mode)
    {
        if (r < x || y < l || tree[ind] + v > dist)
        {
            return;
        }
        if (l == r)
        {
            num++;
            if (mode)
            {
                con.push_back(tree[ind] + v);
            }
            return;
        }
        long long m = (l + r) >> 1;
        Get(ind << 1, l, m, x, y, v, dist, mode);
        if (num < k)
        {
            Get(ind << 1 | 1, m + 1, r, x, y, v, dist, mode);
        }
    }
    inline void Check(long long x, long long y, long long v, long long dist, long long mode)
    {
        num = 0;
        if (mode)
        {
            con.clear();
        }
        if (x <= y)
        {
            Get(1, 1, n, x, y, v, dist, mode);
        }
    }
} st1, st2;

inline bool Comp(const array<long long, 3> &ina, const array<long long, 3> &inb)
{
    return ina[1] < inb[1];
}

inline long long Cal(long long x)
{
    long long cur = 0;
    st1.Init();
    st2.Init();
    for (long long i = 0; i < n && cur <= k; ++i)
    {
        st1.Check(1, p[i][2], p[i][0] + p[i][1], x, 0);
        st1.Set(1, 1, n, p[i][2], -p[i][0] - p[i][1]);
        st2.Check(p[i][2] + 1, n, p[i][0] - p[i][1], x, 0);
        st2.Set(1, 1, n, p[i][2], -p[i][0] + p[i][1]);
        cur += st1.num + st2.num;
    }
    return cur;
}

int main()
{
    setup();

    cin >> n >> k;
    for (long long i = 0; i < n; ++i)
    {
        cin >> p[i][0] >> p[i][1];
    }
    sort(p, p + n, Comp);
    for (long long i = 0; i < n; ++i)
    {
        p[i][2] = i + 1;
    }
    sort(p, p + n);
    lb = 0;
    rb = 4e9;
    while (lb <= rb)
    {
        mid = (lb + rb) >> 1;
        if (Cal(mid) < k)
        {
            lb = mid + 1;
        }
        else
        {
            rb = mid - 1;
            res = mid;
        }
    }
    st1.Init();
    st2.Init();
    for (long long i = 0; i < n; ++i)
    {
        st1.Check(1, p[i][2], p[i][0] + p[i][1], res - 1, 1);
        st1.Set(1, 1, n, p[i][2], -p[i][0] - p[i][1]);
        st2.Check(p[i][2] + 1, n, p[i][0] - p[i][1], res - 1, 1);
        st2.Set(1, 1, n, p[i][2], -p[i][0] + p[i][1]);
        for (auto &j : st1.con)
        {
            g.push_back(j);
        }
        for (auto &j : st2.con)
        {
            g.push_back(j);
        }
    }
    while (g.size() < k)
    {
        g.push_back(res);
    }
    sort(g.begin(), g.end());
    for (auto &i : g)
    {
        cout << i << "\n";
    }
    return 0;
}

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