oj.uz

Submission #415782

# Submission time Handle Problem Language Result Execution time Memory
415782 2021-06-01T13:57:09 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 81228 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;
        int XL[n], XM[n], YM[n];
        int pt = 0;
        for(int i = 0; i < n; ++i)
        {
            while(pt < n && X[pt] < X[i] - mid) ++pt;
            XL[i] = pt;
        }
        pt = 0;
        for(int i = 0; i < n; ++i)
        {
            while(pt < n && X[pt] <= X[i] + mid) ++pt;
            XM[i] = pt;
        }
        pt = 0;
        for(int i = 0; i < n; ++i)
        {
            while(pt < n && Y[pt] <= Y[i] + mid) ++pt;
            YM[i] = pt;
        }
        for(int i = 0; i < n; ++i)
        {
            ans += qr(root[YM[i]], 0, n, XL[Q[i]], XM[Q[i]]) - qr(root[i + 1], 0, n, XL[Q[i]], XM[Q[i]]);
        }

        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 86 ms 5200 KB Output is correct
2 Correct 68 ms 5228 KB Output is correct
3 Correct 57 ms 5188 KB Output is correct
4 Correct 70 ms 5252 KB Output is correct
5 Correct 75 ms 4060 KB Output is correct
6 Correct 12 ms 588 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2425 ms 80944 KB Output is correct
2 Correct 2330 ms 81080 KB Output is correct
3 Correct 51 ms 5068 KB Output is correct
4 Correct 2217 ms 80892 KB Output is correct
5 Correct 2193 ms 80228 KB Output is correct
6 Correct 2274 ms 80304 KB Output is correct
7 Correct 2316 ms 79536 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4781 ms 76892 KB Output is correct
2 Correct 4909 ms 76876 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2301 ms 76480 KB Output is correct
5 Correct 5366 ms 76484 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4781 ms 76892 KB Output is correct
2 Correct 4909 ms 76876 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2301 ms 76480 KB Output is correct
5 Correct 5366 ms 76484 KB Output is correct
6 Correct 5756 ms 76476 KB Output is correct
7 Correct 5717 ms 77244 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 5124 ms 77240 KB Output is correct
11 Correct 2144 ms 77244 KB Output is correct
12 Correct 5230 ms 77240 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5200 KB Output is correct
2 Correct 68 ms 5228 KB Output is correct
3 Correct 57 ms 5188 KB Output is correct
4 Correct 70 ms 5252 KB Output is correct
5 Correct 75 ms 4060 KB Output is correct
6 Correct 12 ms 588 KB Output is correct
7 Correct 3747 ms 33884 KB Output is correct
8 Correct 3771 ms 33880 KB Output is correct
9 Correct 84 ms 5180 KB Output is correct
10 Correct 3361 ms 33124 KB Output is correct
11 Correct 2478 ms 33000 KB Output is correct
12 Correct 2309 ms 33896 KB Output is correct
13 Correct 2028 ms 32380 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5200 KB Output is correct
2 Correct 68 ms 5228 KB Output is correct
3 Correct 57 ms 5188 KB Output is correct
4 Correct 70 ms 5252 KB Output is correct
5 Correct 75 ms 4060 KB Output is correct
6 Correct 12 ms 588 KB Output is correct
7 Correct 2425 ms 80944 KB Output is correct
8 Correct 2330 ms 81080 KB Output is correct
9 Correct 51 ms 5068 KB Output is correct
10 Correct 2217 ms 80892 KB Output is correct
11 Correct 2193 ms 80228 KB Output is correct
12 Correct 2274 ms 80304 KB Output is correct
13 Correct 2316 ms 79536 KB Output is correct
14 Correct 4781 ms 76892 KB Output is correct
15 Correct 4909 ms 76876 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 2301 ms 76480 KB Output is correct
18 Correct 5366 ms 76484 KB Output is correct
19 Correct 5756 ms 76476 KB Output is correct
20 Correct 5717 ms 77244 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct
23 Correct 5124 ms 77240 KB Output is correct
24 Correct 2144 ms 77244 KB Output is correct
25 Correct 5230 ms 77240 KB Output is correct
26 Correct 3747 ms 33884 KB Output is correct
27 Correct 3771 ms 33880 KB Output is correct
28 Correct 84 ms 5180 KB Output is correct
29 Correct 3361 ms 33124 KB Output is correct
30 Correct 2478 ms 33000 KB Output is correct
31 Correct 2309 ms 33896 KB Output is correct
32 Correct 2028 ms 32380 KB Output is correct
33 Correct 8151 ms 81228 KB Output is correct
34 Execution timed out 10039 ms 80052 KB Time limit exceeded
35 Halted 0 ms 0 KB -