oj.uz

답안 #415761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415761 2021-06-01T13:19:48 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 81868 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 x = lower_bound(Y, Y + n, (int)max((long long)Y[i] - mid, (long long)-INF)) - Y;
            int y = upper_bound(Y, Y + n, (int)min((long long)Y[i] + mid, (long long)INF)) - Y;
            int l = lower_bound(X, X + n, (int)max((long long)X[Q[i]] - mid, (long long)-INF)) - X;
            int r = upper_bound(X, X + n, (int)min((long long)X[Q[i]] + mid, (long long)INF)) - X;
            ans += qr(root[y], 0, n, l, r) - qr(root[x], 0, n, l, r);
        }

        if(ans < n + 2 * k) s = mid;
        else e = mid;
    }

    vector<long long> ans;
    for(int i = 0; i < n; ++i)
    {
        int x = lower_bound(Y, Y + n, (int)max((long long)Y[i] - s, (long long)-INF)) - Y;
        int y = upper_bound(Y, Y + n, (int)min((long long)Y[i] + s, (long long)INF)) - Y;
        int l = lower_bound(X, X + n, (int)max((long long)X[Q[i]] - s, (long long)-INF)) - X;
        int r = upper_bound(X, X + n, (int)min((long long)X[Q[i]] + s, (long long)INF)) - X;
        qry(root[x], 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();
    }
    while((int)ans.size() < n + 2 * k) ans.push_back(e);

    sort(ans.begin(), ans.end());
    for(int i = n; i < n + 2 * k; i += 2) cout << ans[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

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 7064 KB Output is correct
2 Correct 120 ms 7136 KB Output is correct
3 Correct 88 ms 7140 KB Output is correct
4 Correct 86 ms 7092 KB Output is correct
5 Correct 100 ms 5924 KB Output is correct
6 Correct 14 ms 588 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3596 ms 81848 KB Output is correct
2 Correct 3739 ms 81868 KB Output is correct
3 Correct 78 ms 7052 KB Output is correct
4 Correct 3478 ms 81860 KB Output is correct
5 Correct 3816 ms 81840 KB Output is correct
6 Correct 3786 ms 81812 KB Output is correct
7 Correct 3733 ms 81840 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9660 ms 75720 KB Output is correct
2 Correct 8672 ms 75708 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3677 ms 75728 KB Output is correct
5 Correct 7845 ms 75712 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9660 ms 75720 KB Output is correct
2 Correct 8672 ms 75708 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3677 ms 75728 KB Output is correct
5 Correct 7845 ms 75712 KB Output is correct
6 Correct 8421 ms 75688 KB Output is correct
7 Correct 8488 ms 75704 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 9107 ms 75748 KB Output is correct
11 Correct 3536 ms 75716 KB Output is correct
12 Correct 7905 ms 75676 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 7064 KB Output is correct
2 Correct 120 ms 7136 KB Output is correct
3 Correct 88 ms 7140 KB Output is correct
4 Correct 86 ms 7092 KB Output is correct
5 Correct 100 ms 5924 KB Output is correct
6 Correct 14 ms 588 KB Output is correct
7 Correct 5541 ms 36420 KB Output is correct
8 Correct 5236 ms 36400 KB Output is correct
9 Correct 85 ms 7188 KB Output is correct
10 Correct 4478 ms 36476 KB Output is correct
11 Correct 3978 ms 36424 KB Output is correct
12 Correct 3605 ms 36412 KB Output is correct
13 Correct 2969 ms 36420 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 7064 KB Output is correct
2 Correct 120 ms 7136 KB Output is correct
3 Correct 88 ms 7140 KB Output is correct
4 Correct 86 ms 7092 KB Output is correct
5 Correct 100 ms 5924 KB Output is correct
6 Correct 14 ms 588 KB Output is correct
7 Correct 3596 ms 81848 KB Output is correct
8 Correct 3739 ms 81868 KB Output is correct
9 Correct 78 ms 7052 KB Output is correct
10 Correct 3478 ms 81860 KB Output is correct
11 Correct 3816 ms 81840 KB Output is correct
12 Correct 3786 ms 81812 KB Output is correct
13 Correct 3733 ms 81840 KB Output is correct
14 Correct 9660 ms 75720 KB Output is correct
15 Correct 8672 ms 75708 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3677 ms 75728 KB Output is correct
18 Correct 7845 ms 75712 KB Output is correct
19 Correct 8421 ms 75688 KB Output is correct
20 Correct 8488 ms 75704 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 9107 ms 75748 KB Output is correct
24 Correct 3536 ms 75716 KB Output is correct
25 Correct 7905 ms 75676 KB Output is correct
26 Correct 5541 ms 36420 KB Output is correct
27 Correct 5236 ms 36400 KB Output is correct
28 Correct 85 ms 7188 KB Output is correct
29 Correct 4478 ms 36476 KB Output is correct
30 Correct 3978 ms 36424 KB Output is correct
31 Correct 3605 ms 36412 KB Output is correct
32 Correct 2969 ms 36420 KB Output is correct
33 Execution timed out 10020 ms 73444 KB Time limit exceeded
34 Halted 0 ms 0 KB -