oj.uz

답안 #434853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434853 2021-06-22T01:49:58 Z blue Road Construction (JOI21_road_construction) C++17
12 / 100
 10000 ms 27032 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 = 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 = Kval;
      |                 ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3311 ms 23764 KB Output is correct
2 Correct 3265 ms 23768 KB Output is correct
3 Correct 3127 ms 23868 KB Output is correct
4 Correct 2952 ms 23884 KB Output is correct
5 Correct 3171 ms 22612 KB Output is correct
6 Correct 39 ms 19160 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10066 ms 27032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3378 ms 24964 KB Output is correct
2 Correct 5305 ms 24960 KB Output is correct
3 Correct 12 ms 19020 KB Output is correct
4 Correct 3331 ms 24964 KB Output is correct
5 Correct 3255 ms 24964 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3378 ms 24964 KB Output is correct
2 Correct 5305 ms 24960 KB Output is correct
3 Correct 12 ms 19020 KB Output is correct
4 Correct 3331 ms 24964 KB Output is correct
5 Correct 3255 ms 24964 KB Output is correct
6 Correct 5647 ms 24968 KB Output is correct
7 Correct 5266 ms 25028 KB Output is correct
8 Correct 10 ms 19020 KB Output is correct
9 Correct 10 ms 19020 KB Output is correct
10 Correct 5337 ms 24964 KB Output is correct
11 Correct 1796 ms 24964 KB Output is correct
12 Incorrect 3560 ms 24964 KB Output isn't correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3311 ms 23764 KB Output is correct
2 Correct 3265 ms 23768 KB Output is correct
3 Correct 3127 ms 23868 KB Output is correct
4 Correct 2952 ms 23884 KB Output is correct
5 Correct 3171 ms 22612 KB Output is correct
6 Correct 39 ms 19160 KB Output is correct
7 Correct 8776 ms 25424 KB Output is correct
8 Correct 8805 ms 25464 KB Output is correct
9 Correct 2919 ms 23892 KB Output is correct
10 Incorrect 7196 ms 24840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3311 ms 23764 KB Output is correct
2 Correct 3265 ms 23768 KB Output is correct
3 Correct 3127 ms 23868 KB Output is correct
4 Correct 2952 ms 23884 KB Output is correct
5 Correct 3171 ms 22612 KB Output is correct
6 Correct 39 ms 19160 KB Output is correct
7 Execution timed out 10066 ms 27032 KB Time limit exceeded
8 Halted 0 ms 0 KB -