oj.uz

Submission #415766

# Submission time Handle Problem Language Result Execution time Memory
415766 2021-06-01T13:30:33 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 78140 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 77 ms 5168 KB Output is correct
2 Correct 80 ms 5120 KB Output is correct
3 Correct 79 ms 5156 KB Output is correct
4 Correct 63 ms 5168 KB Output is correct
5 Correct 76 ms 4016 KB Output is correct
6 Correct 14 ms 536 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3235 ms 78104 KB Output is correct
2 Correct 3180 ms 78140 KB Output is correct
3 Correct 53 ms 5036 KB Output is correct
4 Correct 3165 ms 77948 KB Output is correct
5 Correct 3397 ms 78140 KB Output is correct
6 Correct 3353 ms 78100 KB Output is correct
7 Correct 3371 ms 77372 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7894 ms 75924 KB Output is correct
2 Correct 7237 ms 75332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 3465 ms 75336 KB Output is correct
5 Correct 7311 ms 75464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7894 ms 75924 KB Output is correct
2 Correct 7237 ms 75332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 3465 ms 75336 KB Output is correct
5 Correct 7311 ms 75464 KB Output is correct
6 Correct 7879 ms 75588 KB Output is correct
7 Correct 8387 ms 75660 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 7837 ms 75636 KB Output is correct
11 Correct 3361 ms 75624 KB Output is correct
12 Correct 7721 ms 75516 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5168 KB Output is correct
2 Correct 80 ms 5120 KB Output is correct
3 Correct 79 ms 5156 KB Output is correct
4 Correct 63 ms 5168 KB Output is correct
5 Correct 76 ms 4016 KB Output is correct
6 Correct 14 ms 536 KB Output is correct
7 Correct 5218 ms 34236 KB Output is correct
8 Correct 5099 ms 34256 KB Output is correct
9 Correct 59 ms 5256 KB Output is correct
10 Correct 4570 ms 33444 KB Output is correct
11 Correct 3734 ms 33344 KB Output is correct
12 Correct 3315 ms 34216 KB Output is correct
13 Correct 2784 ms 32720 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5168 KB Output is correct
2 Correct 80 ms 5120 KB Output is correct
3 Correct 79 ms 5156 KB Output is correct
4 Correct 63 ms 5168 KB Output is correct
5 Correct 76 ms 4016 KB Output is correct
6 Correct 14 ms 536 KB Output is correct
7 Correct 3235 ms 78104 KB Output is correct
8 Correct 3180 ms 78140 KB Output is correct
9 Correct 53 ms 5036 KB Output is correct
10 Correct 3165 ms 77948 KB Output is correct
11 Correct 3397 ms 78140 KB Output is correct
12 Correct 3353 ms 78100 KB Output is correct
13 Correct 3371 ms 77372 KB Output is correct
14 Correct 7894 ms 75924 KB Output is correct
15 Correct 7237 ms 75332 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 3465 ms 75336 KB Output is correct
18 Correct 7311 ms 75464 KB Output is correct
19 Correct 7879 ms 75588 KB Output is correct
20 Correct 8387 ms 75660 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 7837 ms 75636 KB Output is correct
24 Correct 3361 ms 75624 KB Output is correct
25 Correct 7721 ms 75516 KB Output is correct
26 Correct 5218 ms 34236 KB Output is correct
27 Correct 5099 ms 34256 KB Output is correct
28 Correct 59 ms 5256 KB Output is correct
29 Correct 4570 ms 33444 KB Output is correct
30 Correct 3734 ms 33344 KB Output is correct
31 Correct 3315 ms 34216 KB Output is correct
32 Correct 2784 ms 32720 KB Output is correct
33 Execution timed out 10027 ms 77720 KB Time limit exceeded
34 Halted 0 ms 0 KB -