oj.uz

Submission #415756

# Submission time Handle Problem Language Result Execution time Memory
415756 2021-06-01T13:08:26 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
38 / 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;
    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:107:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |         long long mid = s + e >> 1;
      |                         ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7128 KB Output is correct
2 Correct 129 ms 7140 KB Output is correct
3 Correct 115 ms 7056 KB Output is correct
4 Correct 117 ms 7188 KB Output is correct
5 Correct 86 ms 5932 KB Output is correct
6 Correct 12 ms 648 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4861 ms 81856 KB Output is correct
2 Correct 4754 ms 81844 KB Output is correct
3 Correct 76 ms 6932 KB Output is correct
4 Correct 4687 ms 81844 KB Output is correct
5 Correct 4693 ms 81844 KB Output is correct
6 Correct 4624 ms 81844 KB Output is correct
7 Correct 4916 ms 81840 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10012 ms 73468 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 10012 ms 73468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7128 KB Output is correct
2 Correct 129 ms 7140 KB Output is correct
3 Correct 115 ms 7056 KB Output is correct
4 Correct 117 ms 7188 KB Output is correct
5 Correct 86 ms 5932 KB Output is correct
6 Correct 12 ms 648 KB Output is correct
7 Correct 5409 ms 36420 KB Output is correct
8 Correct 5121 ms 36364 KB Output is correct
9 Correct 110 ms 7188 KB Output is correct
10 Correct 5086 ms 36428 KB Output is correct
11 Correct 4186 ms 36420 KB Output is correct
12 Correct 3607 ms 36424 KB Output is correct
13 Correct 3191 ms 36416 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7128 KB Output is correct
2 Correct 129 ms 7140 KB Output is correct
3 Correct 115 ms 7056 KB Output is correct
4 Correct 117 ms 7188 KB Output is correct
5 Correct 86 ms 5932 KB Output is correct
6 Correct 12 ms 648 KB Output is correct
7 Correct 4861 ms 81856 KB Output is correct
8 Correct 4754 ms 81844 KB Output is correct
9 Correct 76 ms 6932 KB Output is correct
10 Correct 4687 ms 81844 KB Output is correct
11 Correct 4693 ms 81844 KB Output is correct
12 Correct 4624 ms 81844 KB Output is correct
13 Correct 4916 ms 81840 KB Output is correct
14 Execution timed out 10012 ms 73468 KB Time limit exceeded
15 Halted 0 ms 0 KB -