oj.uz

Submission #415763

# Submission time Handle Problem Language Result Execution time Memory
415763 2021-06-01T13:21:47 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 81856 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 /= 500;
    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

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7128 KB Output is correct
2 Correct 106 ms 7072 KB Output is correct
3 Correct 102 ms 7156 KB Output is correct
4 Correct 94 ms 7204 KB Output is correct
5 Correct 88 ms 5964 KB Output is correct
6 Correct 16 ms 588 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3494 ms 81840 KB Output is correct
2 Correct 3394 ms 81844 KB Output is correct
3 Correct 75 ms 6964 KB Output is correct
4 Correct 3319 ms 81852 KB Output is correct
5 Correct 3520 ms 81840 KB Output is correct
6 Correct 3538 ms 81844 KB Output is correct
7 Correct 3649 ms 81856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9340 ms 75708 KB Output is correct
2 Correct 8833 ms 75716 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3492 ms 75708 KB Output is correct
5 Correct 7369 ms 75708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9340 ms 75708 KB Output is correct
2 Correct 8833 ms 75716 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3492 ms 75708 KB Output is correct
5 Correct 7369 ms 75708 KB Output is correct
6 Correct 8306 ms 75708 KB Output is correct
7 Correct 9027 ms 75700 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 8276 ms 75704 KB Output is correct
11 Correct 3485 ms 75712 KB Output is correct
12 Correct 7378 ms 75716 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7128 KB Output is correct
2 Correct 106 ms 7072 KB Output is correct
3 Correct 102 ms 7156 KB Output is correct
4 Correct 94 ms 7204 KB Output is correct
5 Correct 88 ms 5964 KB Output is correct
6 Correct 16 ms 588 KB Output is correct
7 Correct 5545 ms 36420 KB Output is correct
8 Correct 5266 ms 36376 KB Output is correct
9 Correct 87 ms 7192 KB Output is correct
10 Correct 5142 ms 36364 KB Output is correct
11 Correct 4532 ms 36408 KB Output is correct
12 Correct 3521 ms 36360 KB Output is correct
13 Correct 3017 ms 36444 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7128 KB Output is correct
2 Correct 106 ms 7072 KB Output is correct
3 Correct 102 ms 7156 KB Output is correct
4 Correct 94 ms 7204 KB Output is correct
5 Correct 88 ms 5964 KB Output is correct
6 Correct 16 ms 588 KB Output is correct
7 Correct 3494 ms 81840 KB Output is correct
8 Correct 3394 ms 81844 KB Output is correct
9 Correct 75 ms 6964 KB Output is correct
10 Correct 3319 ms 81852 KB Output is correct
11 Correct 3520 ms 81840 KB Output is correct
12 Correct 3538 ms 81844 KB Output is correct
13 Correct 3649 ms 81856 KB Output is correct
14 Correct 9340 ms 75708 KB Output is correct
15 Correct 8833 ms 75716 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3492 ms 75708 KB Output is correct
18 Correct 7369 ms 75708 KB Output is correct
19 Correct 8306 ms 75708 KB Output is correct
20 Correct 9027 ms 75700 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 8276 ms 75704 KB Output is correct
24 Correct 3485 ms 75712 KB Output is correct
25 Correct 7378 ms 75716 KB Output is correct
26 Correct 5545 ms 36420 KB Output is correct
27 Correct 5266 ms 36376 KB Output is correct
28 Correct 87 ms 7192 KB Output is correct
29 Correct 5142 ms 36364 KB Output is correct
30 Correct 4532 ms 36408 KB Output is correct
31 Correct 3521 ms 36360 KB Output is correct
32 Correct 3017 ms 36444 KB Output is correct
33 Execution timed out 10032 ms 73464 KB Time limit exceeded
34 Halted 0 ms 0 KB -