oj.uz

Submission #434852

# Submission time Handle Problem Language Result Execution time Memory
434852 2021-06-22T01:47:46 Z blue Road Construction (JOI21_road_construction) C++17
12 / 100
 9908 ms 28448 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

/*
1. Normalize Y coordinates
Binary search for K'th smallest distance:

WLOG x[1] <= ... <= x[N]
The cost for the point i and the point j is (x[j] - x[i]) + |y[j] - y[i]|.
                    y[i] < y[j]             (x[j] + y[j]) - (x[i] + y[i])    Segtree S
                    y[i] >= y[j]            (x[j] - y[j]) - (x[i] - y[i])    Segtree T

Maintain two segment trees: In one store the x[i] + y[i] values, in the other store the x[i] - y[i]
values.
For each point compute the normalized Y coordinate.
*/

const long long INF = 1'000'000'000'000;
const int maxN = 250000;

struct segtree
{
    pair<int, long long>* v; //range max

    segtree()
    {
        v = new pair<int, long long>[600001];
    }

    void build_segtree(int i, int L, int R)
    {
        v[i] = make_pair(L, -INF);
        if(L == R) return;
        int m = (L+R)/2;
        build_segtree(2*i, L, m);
        build_segtree(2*i+1, m+1, R);
    }

    void update(int i, int l, int r, int I, long long V)
    {
        if(I < l || r < I) return;
        else if(l == r) v[i] = make_pair(l, V);
        else
        {
            update(2*i, l, (l+r)/2, I, V);
            update(2*i+1, (l+r)/2+1, r, I, V);

            pair<int, long long> LP = v[2*i];
            pair<int, long long> RP = v[2*i + 1];

            if(LP.second > RP.second) v[i] = LP;
            else v[i] = RP;
        }
    }

    pair<int, long long> rangemax(int i, int l, int r, int L, int R)
    {
        if(R < l || r < L) return make_pair(-1, -INF);
        else if(L <= l && r <= R) return v[i];
        else
        {
            pair<int, long long> LP = rangemax(2*i, l, (l+r)/2, L, R);
            pair<int, long long> RP = rangemax(2*i + 1, (l+r)/2+1, r, L, R);

            if(LP.second > RP.second) return LP;
            else return RP;
        }
    }
};

int N, K;

struct point
{
    long long X;
    long long Y;
    int Yindex;
};

vector<point> P;

int main()
{
    // cerr << "hello\n";
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;

    P = vector<point>(N);

    for(int i = 0; i < N; i++) cin >> P[i].X >> P[i].Y;

    sort(P.begin(), P.end(), [] (point A, point B)
    {
        return A.Y < B.Y;
    });

    for(int i = 0; i < N; i++) P[i].Yindex = i+1;

    sort(P.begin(), P.end(), [] (point A, point B)
    {
        return A.X < B.X;
    });

    // cerr << "check0\n";

    // for(point p:P) cerr << p.X << ' ' << p.Y << ' ' << p.Yindex << '\n';

    segtree S, T;

    // cerr << "check1\n";

    long long lo = 0, hi = 4'000'000'000LL;
    vector<long long> res;
    while(1)
    {
        long long Kval = (lo+hi)/2;
        res.clear();
        S.build_segtree(1, 1, N);
        T.build_segtree(1, 1, N);

        // cerr << "searching " << lo << ' ' << hi << '\n';


        for(point p:P)
        {
            vector< pair<int, long long> > updates;

            while(res.size() < K)
            {
                pair<int, long long> Q = S.rangemax(1, 1, N, 1, p.Yindex);
                if(Q.second <= -INF) break;

                if((p.X + p.Y) - Q.second > Kval) break;

                res.push_back((p.X + p.Y) - Q.second);

                S.update(1, 1, N, Q.first, -INF);

                updates.push_back(Q);
            }

            for(pair<int, long long> u: updates)
                S.update(1, 1, N, u.first, u.second);

            updates.clear();






            while(res.size() < K)
            {
                pair<int, long long> Q = T.rangemax(1, 1, N, p.Yindex+1, N);
                if(Q.second <= -INF) break;

                if((p.X - p.Y) - Q.second > Kval) break;

                res.push_back((p.X - p.Y) - Q.second);

                T.update(1, 1, N, Q.first, -INF);

                updates.push_back(Q);
            }

            for(pair<int, long long> u: updates)
                T.update(1, 1, N, u.first, u.second);

            updates.clear();






            S.update(1, 1, N, p.Yindex, p.X + p.Y);
            T.update(1, 1, N, p.Yindex, p.X - p.Y);

            if(res.size() >= K) break;
        }

        sort(res.begin(), res.end());
        if(lo == hi)
        {
            break;
        }
        else if(res.size() >= K) hi = min(res[K-1], Kval);
        else lo = Kval + 1;
    }
    for(long long r:res) cout << r << '\n';
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:134:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |             while(res.size() < K)
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:158:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  158 |             while(res.size() < K)
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:185:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  185 |             if(res.size() >= K) break;
      |                ~~~~~~~~~~~^~~~
road_construction.cpp:193:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  193 |         else if(res.size() >= K) hi = min(res[K-1], Kval);
      |                 ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3194 ms 23680 KB Output is correct
2 Correct 3180 ms 23876 KB Output is correct
3 Correct 2971 ms 23884 KB Output is correct
4 Correct 2926 ms 23888 KB Output is correct
5 Correct 2921 ms 22628 KB Output is correct
6 Correct 28 ms 19160 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9908 ms 28448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4219 ms 24964 KB Output is correct
2 Correct 4455 ms 24968 KB Output is correct
3 Correct 9 ms 19020 KB Output is correct
4 Correct 3712 ms 24968 KB Output is correct
5 Correct 6642 ms 24964 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4219 ms 24964 KB Output is correct
2 Correct 4455 ms 24968 KB Output is correct
3 Correct 9 ms 19020 KB Output is correct
4 Correct 3712 ms 24968 KB Output is correct
5 Correct 6642 ms 24964 KB Output is correct
6 Correct 5453 ms 24960 KB Output is correct
7 Correct 5121 ms 24964 KB Output is correct
8 Correct 9 ms 19020 KB Output is correct
9 Correct 9 ms 19044 KB Output is correct
10 Correct 5276 ms 24960 KB Output is correct
11 Correct 3813 ms 25004 KB Output is correct
12 Incorrect 7779 ms 24968 KB Output isn't correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3194 ms 23680 KB Output is correct
2 Correct 3180 ms 23876 KB Output is correct
3 Correct 2971 ms 23884 KB Output is correct
4 Correct 2926 ms 23888 KB Output is correct
5 Correct 2921 ms 22628 KB Output is correct
6 Correct 28 ms 19160 KB Output is correct
7 Correct 8128 ms 25712 KB Output is correct
8 Correct 8258 ms 25460 KB Output is correct
9 Correct 2931 ms 23884 KB Output is correct
10 Incorrect 6949 ms 24812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3194 ms 23680 KB Output is correct
2 Correct 3180 ms 23876 KB Output is correct
3 Correct 2971 ms 23884 KB Output is correct
4 Correct 2926 ms 23888 KB Output is correct
5 Correct 2921 ms 22628 KB Output is correct
6 Correct 28 ms 19160 KB Output is correct
7 Incorrect 9908 ms 28448 KB Output isn't correct
8 Halted 0 ms 0 KB -