oj.uz

Submission #434850

# Submission time Handle Problem Language Result Execution time Memory
434850 2021-06-22T01:35:38 Z blue Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 35364 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
{
    int* l;
    int* r;
    pair<int, long long>* v; //range max

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

    void build_segtree(int i, int L, int R)
    {
        l[i] = L;
        r[i] = R;
        v[i] = make_pair(L, -INF);
        if(l[i] == r[i]) 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 I, long long V)
    {
        if(I < l[i] || r[i] < I) return;
        else if(l[i] == r[i]) v[i] = make_pair(l[i], V);
        else
        {
            update(2*i, I, V);
            update(2*i+1, 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)
    {
        if(R < l[i] || r[i] < L) return make_pair(-1, -INF);
        else if(L <= l[i] && r[i] <= R) return v[i];
        else
        {
            pair<int, long long> LP = rangemax(2*i, L, R);
            pair<int, long long> RP = rangemax(2*i + 1, 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, i, -INF);
            T.update(1, 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, 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, Q.first, -INF);

                updates.push_back(Q);
            }

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

            updates.clear();






            while(res.size() < K)
            {
                pair<int, long long> Q = T.rangemax(1, 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, Q.first, -INF);

                updates.push_back(Q);
            }

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

            updates.clear();






            S.update(1, p.Yindex, p.X + p.Y);
            T.update(1, 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:145:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  145 |             while(res.size() < K)
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:169:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  169 |             while(res.size() < K)
      |                   ~~~~~~~~~~~^~~
road_construction.cpp:196:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  196 |             if(res.size() >= K) break;
      |                ~~~~~~~~~~~^~~~
road_construction.cpp:204:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  204 |         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 3612 ms 23820 KB Output is correct
2 Correct 3606 ms 23856 KB Output is correct
3 Correct 3308 ms 23820 KB Output is correct
4 Correct 3336 ms 23964 KB Output is correct
5 Correct 3315 ms 22708 KB Output is correct
6 Correct 45 ms 19148 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8642 ms 33192 KB Output is correct
2 Correct 9247 ms 33220 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 6902 ms 33188 KB Output is correct
5 Execution timed out 10053 ms 33176 KB Time limit exceeded

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8642 ms 33192 KB Output is correct
2 Correct 9247 ms 33220 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 6902 ms 33188 KB Output is correct
5 Execution timed out 10053 ms 33176 KB Time limit exceeded

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3612 ms 23820 KB Output is correct
2 Correct 3606 ms 23856 KB Output is correct
3 Correct 3308 ms 23820 KB Output is correct
4 Correct 3336 ms 23964 KB Output is correct
5 Correct 3315 ms 22708 KB Output is correct
6 Correct 45 ms 19148 KB Output is correct
7 Execution timed out 10091 ms 28096 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3612 ms 23820 KB Output is correct
2 Correct 3606 ms 23856 KB Output is correct
3 Correct 3308 ms 23820 KB Output is correct
4 Correct 3336 ms 23964 KB Output is correct
5 Correct 3315 ms 22708 KB Output is correct
6 Correct 45 ms 19148 KB Output is correct
7 Execution timed out 10057 ms 35364 KB Time limit exceeded
8 Halted 0 ms 0 KB -