oj.uz

Submission #415753

# Submission time Handle Problem Language Result Execution time Memory
415753 2021-06-01T13:02:31 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 81868 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

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:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int upd(int, int, int, int)':
road_construction.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int qr(int, int, int, int, int)':
road_construction.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'void qry(int, int, int, int, int, int)':
road_construction.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = s + e >> 1;
      |               ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:104:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         long long mid = s + e >> 1;
      |                         ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7072 KB Output is correct
2 Correct 116 ms 7160 KB Output is correct
3 Correct 108 ms 7060 KB Output is correct
4 Correct 94 ms 7180 KB Output is correct
5 Correct 89 ms 5924 KB Output is correct
6 Correct 17 ms 644 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5358 ms 81840 KB Output is correct
2 Correct 5299 ms 81840 KB Output is correct
3 Correct 82 ms 6932 KB Output is correct
4 Correct 5499 ms 81868 KB Output is correct
5 Correct 5720 ms 81844 KB Output is correct
6 Correct 5359 ms 81852 KB Output is correct
7 Correct 5490 ms 81840 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7072 KB Output is correct
2 Correct 116 ms 7160 KB Output is correct
3 Correct 108 ms 7060 KB Output is correct
4 Correct 94 ms 7180 KB Output is correct
5 Correct 89 ms 5924 KB Output is correct
6 Correct 17 ms 644 KB Output is correct
7 Correct 6319 ms 36416 KB Output is correct
8 Correct 5940 ms 36416 KB Output is correct
9 Correct 91 ms 7188 KB Output is correct
10 Correct 5541 ms 36424 KB Output is correct
11 Correct 4674 ms 36420 KB Output is correct
12 Correct 3820 ms 36420 KB Output is correct
13 Correct 3526 ms 36424 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7072 KB Output is correct
2 Correct 116 ms 7160 KB Output is correct
3 Correct 108 ms 7060 KB Output is correct
4 Correct 94 ms 7180 KB Output is correct
5 Correct 89 ms 5924 KB Output is correct
6 Correct 17 ms 644 KB Output is correct
7 Correct 5358 ms 81840 KB Output is correct
8 Correct 5299 ms 81840 KB Output is correct
9 Correct 82 ms 6932 KB Output is correct
10 Correct 5499 ms 81868 KB Output is correct
11 Correct 5720 ms 81844 KB Output is correct
12 Correct 5359 ms 81852 KB Output is correct
13 Correct 5490 ms 81840 KB Output is correct
14 Execution timed out 10056 ms 73536 KB Time limit exceeded
15 Halted 0 ms 0 KB -