oj.uz

Submission #493558

# Submission time Handle Problem Language Result Execution time Memory
493558 2021-12-12T05:29:20 Z blue Road Construction (JOI21_road_construction) C++17
100 / 100
 3697 ms 766140 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 135172 KB Output is correct
2 Correct 488 ms 135268 KB Output is correct
3 Correct 434 ms 129644 KB Output is correct
4 Correct 376 ms 129620 KB Output is correct
5 Correct 458 ms 133968 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2282 ms 762932 KB Output is correct
2 Correct 2138 ms 762860 KB Output is correct
3 Correct 303 ms 129452 KB Output is correct
4 Correct 1442 ms 762856 KB Output is correct
5 Correct 1386 ms 762868 KB Output is correct
6 Correct 1382 ms 762940 KB Output is correct
7 Correct 1435 ms 762440 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2124 ms 539484 KB Output is correct
2 Correct 2129 ms 539476 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 952 ms 537180 KB Output is correct
5 Correct 1372 ms 539612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2124 ms 539484 KB Output is correct
2 Correct 2129 ms 539476 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 952 ms 537180 KB Output is correct
5 Correct 1372 ms 539612 KB Output is correct
6 Correct 2091 ms 539656 KB Output is correct
7 Correct 2150 ms 539492 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2157 ms 539520 KB Output is correct
11 Correct 907 ms 537324 KB Output is correct
12 Correct 1403 ms 539840 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 135172 KB Output is correct
2 Correct 488 ms 135268 KB Output is correct
3 Correct 434 ms 129644 KB Output is correct
4 Correct 376 ms 129620 KB Output is correct
5 Correct 458 ms 133968 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 2088 ms 415840 KB Output is correct
8 Correct 2049 ms 415832 KB Output is correct
9 Correct 414 ms 129992 KB Output is correct
10 Correct 1312 ms 415084 KB Output is correct
11 Correct 1547 ms 414924 KB Output is correct
12 Correct 986 ms 415708 KB Output is correct
13 Correct 1054 ms 414444 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 135172 KB Output is correct
2 Correct 488 ms 135268 KB Output is correct
3 Correct 434 ms 129644 KB Output is correct
4 Correct 376 ms 129620 KB Output is correct
5 Correct 458 ms 133968 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 2282 ms 762932 KB Output is correct
8 Correct 2138 ms 762860 KB Output is correct
9 Correct 303 ms 129452 KB Output is correct
10 Correct 1442 ms 762856 KB Output is correct
11 Correct 1386 ms 762868 KB Output is correct
12 Correct 1382 ms 762940 KB Output is correct
13 Correct 1435 ms 762440 KB Output is correct
14 Correct 2124 ms 539484 KB Output is correct
15 Correct 2129 ms 539476 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 952 ms 537180 KB Output is correct
18 Correct 1372 ms 539612 KB Output is correct
19 Correct 2091 ms 539656 KB Output is correct
20 Correct 2150 ms 539492 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2157 ms 539520 KB Output is correct
24 Correct 907 ms 537324 KB Output is correct
25 Correct 1403 ms 539840 KB Output is correct
26 Correct 2088 ms 415840 KB Output is correct
27 Correct 2049 ms 415832 KB Output is correct
28 Correct 414 ms 129992 KB Output is correct
29 Correct 1312 ms 415084 KB Output is correct
30 Correct 1547 ms 414924 KB Output is correct
31 Correct 986 ms 415708 KB Output is correct
32 Correct 1054 ms 414444 KB Output is correct
33 Correct 3573 ms 766064 KB Output is correct
34 Correct 3697 ms 765960 KB Output is correct
35 Correct 2807 ms 765120 KB Output is correct
36 Correct 1981 ms 766096 KB Output is correct
37 Correct 1907 ms 766140 KB Output is correct
38 Correct 2060 ms 764720 KB Output is correct