oj.uz

Submission #434851

# Submission time Handle Problem Language Result Execution time Memory
434851 2021-06-22T01:42:09 Z blue Road Construction (JOI21_road_construction) C++17
12 / 100
 10000 ms 30244 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;
    S.build_segtree(1, 1, N);
    T.build_segtree(1, 1, N);

    // 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();
        for(int i = 1; i <= N; i++)
        {
            S.update(1, 1, N, i, -INF);
            T.update(1, 1, N, i, -INF);
        }

        // 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:139:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |             while(res.size() < K)
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:163:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  163 |             while(res.size() < K)
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:190:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  190 |             if(res.size() >= K) break;
      |                ~~~~~~~~~~~^~~~
road_construction.cpp:198:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  198 |         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 3190 ms 23864 KB Output is correct
2 Correct 3253 ms 23728 KB Output is correct
3 Correct 2971 ms 23748 KB Output is correct
4 Correct 2995 ms 23940 KB Output is correct
5 Correct 2939 ms 22744 KB Output is correct
6 Correct 36 ms 19124 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10058 ms 27068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6043 ms 24964 KB Output is correct
2 Correct 6518 ms 24960 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 4821 ms 24964 KB Output is correct
5 Correct 9032 ms 24964 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6043 ms 24964 KB Output is correct
2 Correct 6518 ms 24960 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 4821 ms 24964 KB Output is correct
5 Correct 9032 ms 24964 KB Output is correct
6 Correct 8144 ms 30052 KB Output is correct
7 Correct 7752 ms 30052 KB Output is correct
8 Correct 10 ms 19020 KB Output is correct
9 Correct 10 ms 19020 KB Output is correct
10 Correct 7806 ms 30052 KB Output is correct
11 Correct 5037 ms 27908 KB Output is correct
12 Execution timed out 10100 ms 30244 KB Time limit exceeded

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3190 ms 23864 KB Output is correct
2 Correct 3253 ms 23728 KB Output is correct
3 Correct 2971 ms 23748 KB Output is correct
4 Correct 2995 ms 23940 KB Output is correct
5 Correct 2939 ms 22744 KB Output is correct
6 Correct 36 ms 19124 KB Output is correct
7 Correct 9349 ms 25456 KB Output is correct
8 Correct 9719 ms 27492 KB Output is correct
9 Correct 2959 ms 23956 KB Output is correct
10 Incorrect 8116 ms 26740 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3190 ms 23864 KB Output is correct
2 Correct 3253 ms 23728 KB Output is correct
3 Correct 2971 ms 23748 KB Output is correct
4 Correct 2995 ms 23940 KB Output is correct
5 Correct 2939 ms 22744 KB Output is correct
6 Correct 36 ms 19124 KB Output is correct
7 Execution timed out 10058 ms 27068 KB Time limit exceeded
8 Halted 0 ms 0 KB -