Submission #493558

#	Time	Username	Problem	Language	Result	Execution time	Memory
493558		blue	Road Construction (JOI21_road_construction)	C++17	100 / 100	3697 ms	766140 KiB

road_construction

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;

const ll INF = 1'000'000'000'000LL;
const int mx = 250'000;

ll X[1+mx], Y[1+mx];

struct segtree
{
    int l;
    int r;
    pair<ll, int> mn;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        mn = {INF, l};
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    segtree(int L, int R, pair<ll, int> MN, segtree* LF, segtree* RG)
    {
        l = L;
        r = R;
        mn = MN;
        left = LF;
        right = RG;
    }

    segtree* set_value(int I, ll V)
    {
        if(l == r)
        {
            return new segtree(l, r, {V, I}, left, right);
        }
        else if(I <= (l+r)/2)
        {
            segtree* new_left = left->set_value(I, V);
            return new segtree(l, r, min(new_left->mn, right->mn), new_left, right);
        }
        else
        {
            segtree* new_right = right->set_value(I, V);
            return new segtree(l, r, min(left->mn, new_right->mn), left, new_right);
        }
    }

    pair<ll, int> rangemin(int L, int R)
    {
        if(R < l || r < L || R < L) return {2*INF, -1};
        else if(L <= l && r <= R) return mn;
        else return min(left->rangemin(L, R), right->rangemin(L, R));
    }
};

int N, K;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;

    vector<pii> P(N);
    for(int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;
    sort(P.begin(), P.end());
    for(int i = 1; i <= N; i++)
    {
        X[i] = P[i-1].first;
        Y[i] = P[i-1].second;
    }

    vector<int> I(N);
    for(int i = 0; i < N; i++) I[i] = i+1;
    sort(I.begin(), I.end(), [] (int p, int q)
    {
        return Y[p] < Y[q];
    });

    segtree* S1[1+N]; //segtree over X, sweep line over Y
    segtree* S2[1+N];
    // S1[0] = new segtree(1, N);
    // S2[0] = new segtree(1, N);

    S1[I[0]] = new segtree(1, N);
    S2[I[0]] = new segtree(1, N);

    for(int j = 1; j < N; j++)
    {
        int i = I[j];
        int i2 = I[j-1];

        S1[i] = S1[i2]->set_value(i2, -X[i2] - Y[i2]);
        S2[i] = S2[i2]->set_value(i2, +X[i2] - Y[i2]);
    }

    set< pair<ll, int> > tbv;
    for(int i = 1; i <= N; i++)
    {
        tbv.insert({X[i] + Y[i] + S1[i]->rangemin(1, i-1).first, i});
        tbv.insert({-X[i] + Y[i] + S2[i]->rangemin(i+1, N).first, -i});
    }

    vector<ll> res;

    // cerr << "reordered points: \n";
    // for(int i = 1; i <= N; i++) cerr << X[i] << ' ' << Y[i] << '\n';


    for(int j = 1; j <= K; j++)
    {
        auto u = *tbv.begin();
        tbv.erase(u);

        ll v = u.first;
        int i = u.second;

        // cerr << "j = " << j << "\n";
        // cerr << "best up point: " << i << ' ' << v << '\n';

        res.push_back(v);

        if(i > 0)
        {
            // cerr << "segtree = ";
            // for(int q = 1; q <= N; q++) cerr << S1[i]->rangemin(q, q).first << "/" << S1[i]->rangemin(q,q).second << ' ';
            // cerr << '\n';
            // auto f = S1[i].rangemin(1, i-1);
            S1[i] = S1[i]->set_value(S1[i]->rangemin(1, i-1).second, +INF);
            tbv.insert({X[i] + Y[i] + S1[i]->rangemin(1, i-1).first, i});
        }
        else
        {
            S2[-i] = S2[-i]->set_value(S2[-i]->rangemin((-i)+1, N).second, +INF);
            tbv.insert({-X[-i] + Y[-i] + S2[-i]->rangemin((-i)+1, N).first, i});
        }
    }

    for(ll r: res) cout << r << '\n';
}

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