oj.uz

Submission #415787

# Submission time Handle Problem Language Result Execution time Memory
415787 2021-06-01T13:59:38 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 76480 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 XL[n], XM[n], YM[n];
        int pt = 0;
        for(int i = 0; i < n; ++i)
        {
            while(pt < n && X[pt] < X[i] - s) ++pt;
            XL[i] = pt;
        }
        pt = 0;
        for(int i = 0; i < n; ++i)
        {
            while(pt < n && X[pt] <= X[i] + s) ++pt;
            XM[i] = pt;
        }
        pt = 0;
        for(int i = 0; i < n; ++i)
        {
            while(pt < n && Y[pt] <= Y[i] + s) ++pt;
            YM[i] = pt;
        }
        qry(root[i + 1], root[YM[i]], 0, n, XL[Q[i]], XM[Q[i]]);
//        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 92 ms 5144 KB Output is correct
2 Correct 88 ms 5096 KB Output is correct
3 Correct 66 ms 5176 KB Output is correct
4 Correct 57 ms 5232 KB Output is correct
5 Correct 74 ms 4156 KB Output is correct
6 Correct 17 ms 528 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10073 ms 76480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10075 ms 76372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10075 ms 76372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5144 KB Output is correct
2 Correct 88 ms 5096 KB Output is correct
3 Correct 66 ms 5176 KB Output is correct
4 Correct 57 ms 5232 KB Output is correct
5 Correct 74 ms 4156 KB Output is correct
6 Correct 17 ms 528 KB Output is correct
7 Execution timed out 10051 ms 29292 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5144 KB Output is correct
2 Correct 88 ms 5096 KB Output is correct
3 Correct 66 ms 5176 KB Output is correct
4 Correct 57 ms 5232 KB Output is correct
5 Correct 74 ms 4156 KB Output is correct
6 Correct 17 ms 528 KB Output is correct
7 Execution timed out 10073 ms 76480 KB Time limit exceeded
8 Halted 0 ms 0 KB -