oj.uz

Submission #415777

# Submission time Handle Problem Language Result Execution time Memory
415777 2021-06-01T13:48:00 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 78660 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <cstdlib>
#include <set>
#include <cmath>
#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 /= ((int)sqrt(n) - 100);
    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:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int upd(int, int, int, int)':
road_construction.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int qr(int, int, int, int, int)':
road_construction.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'void qry(int, int, int, int, int, int)':
road_construction.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:109:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         long long mid = s + e >> 1;
      |                         ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5164 KB Output is correct
2 Correct 84 ms 5188 KB Output is correct
3 Correct 79 ms 5208 KB Output is correct
4 Correct 67 ms 5172 KB Output is correct
5 Correct 61 ms 3988 KB Output is correct
6 Correct 11 ms 596 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3227 ms 76796 KB Output is correct
2 Correct 3133 ms 77748 KB Output is correct
3 Correct 62 ms 5000 KB Output is correct
4 Correct 3009 ms 77628 KB Output is correct
5 Correct 3310 ms 77776 KB Output is correct
6 Correct 3398 ms 77688 KB Output is correct
7 Correct 3349 ms 76852 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6757 ms 73544 KB Output is correct
2 Correct 6479 ms 73544 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3222 ms 73540 KB Output is correct
5 Correct 7280 ms 73540 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6757 ms 73544 KB Output is correct
2 Correct 6479 ms 73544 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3222 ms 73540 KB Output is correct
5 Correct 7280 ms 73540 KB Output is correct
6 Correct 7314 ms 73544 KB Output is correct
7 Correct 7578 ms 74564 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 6786 ms 74568 KB Output is correct
11 Correct 3046 ms 74564 KB Output is correct
12 Correct 7633 ms 74564 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5164 KB Output is correct
2 Correct 84 ms 5188 KB Output is correct
3 Correct 79 ms 5208 KB Output is correct
4 Correct 67 ms 5172 KB Output is correct
5 Correct 61 ms 3988 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 4940 ms 32716 KB Output is correct
8 Correct 4833 ms 32632 KB Output is correct
9 Correct 61 ms 5192 KB Output is correct
10 Correct 4354 ms 32016 KB Output is correct
11 Correct 3258 ms 31812 KB Output is correct
12 Correct 3487 ms 32716 KB Output is correct
13 Correct 2894 ms 31224 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5164 KB Output is correct
2 Correct 84 ms 5188 KB Output is correct
3 Correct 79 ms 5208 KB Output is correct
4 Correct 67 ms 5172 KB Output is correct
5 Correct 61 ms 3988 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 3227 ms 76796 KB Output is correct
8 Correct 3133 ms 77748 KB Output is correct
9 Correct 62 ms 5000 KB Output is correct
10 Correct 3009 ms 77628 KB Output is correct
11 Correct 3310 ms 77776 KB Output is correct
12 Correct 3398 ms 77688 KB Output is correct
13 Correct 3349 ms 76852 KB Output is correct
14 Correct 6757 ms 73544 KB Output is correct
15 Correct 6479 ms 73544 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3222 ms 73540 KB Output is correct
18 Correct 7280 ms 73540 KB Output is correct
19 Correct 7314 ms 73544 KB Output is correct
20 Correct 7578 ms 74564 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 6786 ms 74568 KB Output is correct
24 Correct 3046 ms 74564 KB Output is correct
25 Correct 7633 ms 74564 KB Output is correct
26 Correct 4940 ms 32716 KB Output is correct
27 Correct 4833 ms 32632 KB Output is correct
28 Correct 61 ms 5192 KB Output is correct
29 Correct 4354 ms 32016 KB Output is correct
30 Correct 3258 ms 31812 KB Output is correct
31 Correct 3487 ms 32716 KB Output is correct
32 Correct 2894 ms 31224 KB Output is correct
33 Execution timed out 10051 ms 78660 KB Time limit exceeded
34 Halted 0 ms 0 KB -