oj.uz

Submission #415760

# Submission time Handle Problem Language Result Execution time Memory
415760 2021-06-01T13:18:35 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
45 / 100
 10000 ms 81848 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 /= 100;
    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 127 ms 7136 KB Output is correct
2 Correct 119 ms 7148 KB Output is correct
3 Correct 88 ms 7112 KB Output is correct
4 Correct 96 ms 7196 KB Output is correct
5 Correct 97 ms 6076 KB Output is correct
6 Correct 15 ms 648 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3884 ms 81848 KB Output is correct
2 Correct 3864 ms 81848 KB Output is correct
3 Correct 81 ms 6980 KB Output is correct
4 Correct 3716 ms 81844 KB Output is correct
5 Correct 4032 ms 81844 KB Output is correct
6 Correct 4040 ms 81844 KB Output is correct
7 Correct 4234 ms 81840 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9807 ms 75708 KB Output is correct
2 Correct 9492 ms 75712 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4244 ms 75712 KB Output is correct
5 Correct 8595 ms 75676 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9807 ms 75708 KB Output is correct
2 Correct 9492 ms 75712 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4244 ms 75712 KB Output is correct
5 Correct 8595 ms 75676 KB Output is correct
6 Execution timed out 10075 ms 75640 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 7136 KB Output is correct
2 Correct 119 ms 7148 KB Output is correct
3 Correct 88 ms 7112 KB Output is correct
4 Correct 96 ms 7196 KB Output is correct
5 Correct 97 ms 6076 KB Output is correct
6 Correct 15 ms 648 KB Output is correct
7 Correct 5208 ms 36416 KB Output is correct
8 Correct 4738 ms 36420 KB Output is correct
9 Correct 89 ms 7188 KB Output is correct
10 Correct 4951 ms 36416 KB Output is correct
11 Correct 4390 ms 36424 KB Output is correct
12 Correct 3573 ms 36400 KB Output is correct
13 Correct 2912 ms 36420 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 7136 KB Output is correct
2 Correct 119 ms 7148 KB Output is correct
3 Correct 88 ms 7112 KB Output is correct
4 Correct 96 ms 7196 KB Output is correct
5 Correct 97 ms 6076 KB Output is correct
6 Correct 15 ms 648 KB Output is correct
7 Correct 3884 ms 81848 KB Output is correct
8 Correct 3864 ms 81848 KB Output is correct
9 Correct 81 ms 6980 KB Output is correct
10 Correct 3716 ms 81844 KB Output is correct
11 Correct 4032 ms 81844 KB Output is correct
12 Correct 4040 ms 81844 KB Output is correct
13 Correct 4234 ms 81840 KB Output is correct
14 Correct 9807 ms 75708 KB Output is correct
15 Correct 9492 ms 75712 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4244 ms 75712 KB Output is correct
18 Correct 8595 ms 75676 KB Output is correct
19 Execution timed out 10075 ms 75640 KB Time limit exceeded
20 Halted 0 ms 0 KB -