oj.uz

Submission #415767

# Submission time Handle Problem Language Result Execution time Memory
415767 2021-06-01T13:32:21 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 78136 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <cstdlib>
#include <set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

using namespace std;

const long long INF = (int)2e9 + 7;

struct Node
{
    int x;
    int l, r;
}seg[30202020];
int cnt = 0;

int init(int s, int e)
{
    int ind = cnt++;
    seg[ind].x = 0;
    if(s + 1 == e) return ind;

    int mid = s + e >> 1;
    seg[ind].l = init(s, mid);
    seg[ind].r = init(mid, e);
    return ind;
}

int upd(int nd, int s, int e, int pos)
{
    int ind = cnt++;
    seg[ind] = seg[nd];
    if(s + 1 == e)
    {
        ++seg[ind].x;
        return ind;
    }

    int mid = s + e >> 1;
    if(pos < mid) seg[ind].l = upd(seg[ind].l, s, mid, pos);
    else seg[ind].r = upd(seg[ind].r, mid, e, pos);
    seg[ind].x = seg[seg[ind].l].x + seg[seg[ind].r].x;
    return ind;
}

int qr(int ind, int s, int e, int l, int r)
{
    if(e <= l || r <= s) return 0;
    if(l <= s && e <= r) return seg[ind].x;

    int mid = s + e >> 1;
    return qr(seg[ind].l, s, mid, l, r) + qr(seg[ind].r, mid, e, l, r);
}

vector<int> V;
void qry(int ind1, int ind2, int s, int e, int l, int r)
{
    if(e <= l || r <= s || seg[ind1].x == seg[ind2].x) return;
    if(s + 1 == e) { V.push_back(s); return; }
    int mid = s + e >> 1;
    qry(seg[ind1].l, seg[ind2].l, s, mid, l, r);
    qry(seg[ind1].r, seg[ind2].r, mid, e, l, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;
    pii B[n], C[n];
    for(int i = 0; i < n; ++i) B[i] = {A[i].ff + A[i].ss, i}, C[i] = {A[i].ff - A[i].ss, i};
    sort(B, B + n);
    sort(C, C + n);
    int X[n], Y[n];
    for(int i = 0; i < n; ++i) X[i] = B[i].ff, Y[i] = C[i].ff;
    int P[n]; for(int i = 0; i < n; ++i) P[B[i].ss] = i;
    int Q[n]; for(int i = 0; i < n; ++i) Q[i] = P[C[i].ss];
    int R[n]; for(int i = 0; i < n; ++i) R[Q[i]] = i;

    int root[n + 1];
    root[0] = init(0, n);
    for(int i = 0; i < n; ++i) root[i + 1] = upd(root[i], 0, n, Q[i]);

    long long s = 0, e = 2ll * INF;
    if(n > 100'000) e /= 200;
    while(s + 1 < e)
    {
        long long mid = s + e >> 1;
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int y = upper_bound(Y, Y + n, (int)min((long long)Y[i] + mid, INF)) - Y;
            int l = lower_bound(X, X + n, (int)max((long long)X[Q[i]] - mid, -INF)) - X;
            int r = upper_bound(X, X + n, (int)min((long long)X[Q[i]] + mid, INF)) - X;
            ans += qr(root[y], 0, n, l, r) - qr(root[i + 1], 0, n, l, r);
        }

        if(ans < k) s = mid;
        else e = mid;
    }

    vector<long long> ans;
    for(int i = 0; i < n; ++i)
    {
        int y = upper_bound(Y, Y + n, (int)min((long long)Y[i] + s, INF)) - Y;
        int l = lower_bound(X, X + n, (int)max((long long)X[Q[i]] - s, -INF)) - X;
        int r = upper_bound(X, X + n, (int)min((long long)X[Q[i]] + s, INF)) - X;
        qry(root[i + 1], root[y], 0, n, l, r);
//        for(auto j : V) cout << j << ' '; cout << endl;
        for(auto j : V) ans.push_back(max(abs(1ll * X[j] - X[Q[i]]), abs(1ll * Y[i] - Y[R[j]])));
        V.clear();
    }

    sort(ans.begin(), ans.end());
    while((int)ans.size() < k) ans.push_back(e);
    for(auto i : ans) cout << i << '\n';
}

Compilation message

road_construction.cpp: In function 'int init(int, int)':
road_construction.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int upd(int, int, int, int)':
road_construction.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int qr(int, int, int, int, int)':
road_construction.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'void qry(int, int, int, int, int, int)':
road_construction.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:108:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         long long mid = s + e >> 1;
      |                         ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5136 KB Output is correct
2 Correct 72 ms 5208 KB Output is correct
3 Correct 69 ms 5236 KB Output is correct
4 Correct 60 ms 5256 KB Output is correct
5 Correct 62 ms 4048 KB Output is correct
6 Correct 12 ms 540 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3141 ms 78068 KB Output is correct
2 Correct 3177 ms 78080 KB Output is correct
3 Correct 52 ms 5084 KB Output is correct
4 Correct 3089 ms 77880 KB Output is correct
5 Correct 3143 ms 78136 KB Output is correct
6 Correct 3224 ms 78120 KB Output is correct
7 Correct 3303 ms 77380 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7543 ms 74320 KB Output is correct
2 Correct 6691 ms 73904 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3158 ms 73664 KB Output is correct
5 Correct 7509 ms 73536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7543 ms 74320 KB Output is correct
2 Correct 6691 ms 73904 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3158 ms 73664 KB Output is correct
5 Correct 7509 ms 73536 KB Output is correct
6 Correct 7677 ms 73536 KB Output is correct
7 Correct 7951 ms 73536 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 7204 ms 73536 KB Output is correct
11 Correct 3040 ms 73548 KB Output is correct
12 Correct 7488 ms 73536 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5136 KB Output is correct
2 Correct 72 ms 5208 KB Output is correct
3 Correct 69 ms 5236 KB Output is correct
4 Correct 60 ms 5256 KB Output is correct
5 Correct 62 ms 4048 KB Output is correct
6 Correct 12 ms 540 KB Output is correct
7 Correct 4504 ms 32128 KB Output is correct
8 Correct 4607 ms 32184 KB Output is correct
9 Correct 61 ms 5200 KB Output is correct
10 Correct 4152 ms 31440 KB Output is correct
11 Correct 3468 ms 31400 KB Output is correct
12 Correct 3152 ms 32200 KB Output is correct
13 Correct 2743 ms 30668 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5136 KB Output is correct
2 Correct 72 ms 5208 KB Output is correct
3 Correct 69 ms 5236 KB Output is correct
4 Correct 60 ms 5256 KB Output is correct
5 Correct 62 ms 4048 KB Output is correct
6 Correct 12 ms 540 KB Output is correct
7 Correct 3141 ms 78068 KB Output is correct
8 Correct 3177 ms 78080 KB Output is correct
9 Correct 52 ms 5084 KB Output is correct
10 Correct 3089 ms 77880 KB Output is correct
11 Correct 3143 ms 78136 KB Output is correct
12 Correct 3224 ms 78120 KB Output is correct
13 Correct 3303 ms 77380 KB Output is correct
14 Correct 7543 ms 74320 KB Output is correct
15 Correct 6691 ms 73904 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3158 ms 73664 KB Output is correct
18 Correct 7509 ms 73536 KB Output is correct
19 Correct 7677 ms 73536 KB Output is correct
20 Correct 7951 ms 73536 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 7204 ms 73536 KB Output is correct
24 Correct 3040 ms 73548 KB Output is correct
25 Correct 7488 ms 73536 KB Output is correct
26 Correct 4504 ms 32128 KB Output is correct
27 Correct 4607 ms 32184 KB Output is correct
28 Correct 61 ms 5200 KB Output is correct
29 Correct 4152 ms 31440 KB Output is correct
30 Correct 3468 ms 31400 KB Output is correct
31 Correct 3152 ms 32200 KB Output is correct
32 Correct 2743 ms 30668 KB Output is correct
33 Execution timed out 10057 ms 73496 KB Time limit exceeded
34 Halted 0 ms 0 KB -