oj.uz

Submission #415738

# Submission time Handle Problem Language Result Execution time Memory
415738 2021-06-01T12:29:43 Z 반딧불(#7611) Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 255916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll LIM = 1000000000000000;

int l[40000000], r[40000000];
ll s[40000000], e[40000000];
int val[40000000];
int nodeCnt = 0;

ll locList[250002];
int root[250002];
int rootCnt;

int newNode(ll _s, ll _e, int _v=0, int _l=0, int _r=0){
    nodeCnt++;
    s[nodeCnt] = _s, e[nodeCnt] = _e, val[nodeCnt] = _v;
    l[nodeCnt] = _l, r[nodeCnt] = _r;
    return nodeCnt;
}

void addPoint(int i, ll x){
    if(s[i] == e[i]){
        val[i]++;
        return;
    }
    ll m = (s[i] + e[i] + LIM + LIM) / 2 - LIM;
    if(x <= m){
        l[i] = newNode(s[i], m, val[l[i]], l[l[i]], r[l[i]]);
        addPoint(l[i], x);
    }
    else{
        r[i] = newNode(m+1, e[i], val[r[i]], l[r[i]], r[r[i]]);
        addPoint(r[i], x);
    }
    val[i] = val[l[i]] + val[r[i]];
}

int sum(int i, ll rs, ll re){
    if(rs <= s[i] && e[i] <= re) return val[i];
    ll m = (s[i] + e[i] + LIM + LIM) / 2 - LIM;
    int ret = 0;
    if(rs <= m && l[i]) ret += sum(l[i], rs, re);
    if(m < re && r[i]) ret += sum(r[i], rs, re);
    return ret;
}

void newPoint(ll x, ll y){
    if(locList[rootCnt] != x){
        root[rootCnt+1] = newNode(-1e10, 1e10, val[root[rootCnt]], l[root[rootCnt]], r[root[rootCnt]]);
        locList[++rootCnt] = x;
    }
    addPoint(root[rootCnt], y);
}

int sum(ll xs, ll xe, ll ys, ll ye){
    xe = upper_bound(locList, locList+rootCnt+1, xe) - locList - 1;
    xs = lower_bound(locList, locList+rootCnt+1, xs) - locList - 1;
    return sum(root[xe], ys, ye) - sum(root[xs], ys, ye);
}

int n, k;
pair<ll, ll> arr[250002];
int cnt[250002];
ll minDist[250002];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
        ll tx = arr[i].first, ty = arr[i].second;
        arr[i].first = tx + ty, arr[i].second = tx - ty;
    }

    sort(arr+1, arr+n+1);

    locList[0] = -1e15;
    root[0] = newNode(-1e10, 1e10);
    for(int i=1; i<=n; i++){
        newPoint(arr[i].first, arr[i].second);
    }

    for(int i=1; i<=n; i++){
        ll MIN = 0, MAX = 1e10, ANS = 1e10;
        cnt[i]++;
        while(MIN <= MAX){
            ll MID = (MIN + MAX) / 2;
            if(sum(arr[i].first - MID, arr[i].first + MID, arr[i].second - MID, arr[i].second + MID) > cnt[i]){
                ANS = MID;
                MAX = MID-1;
            }
            else MIN = MID+1;
        }
        minDist[i] = ANS;
        pq.push(make_pair(ANS, i));
    }

    k *= 2;
    while(k--){
        assert(!pq.empty());
        pair<ll, int> p = pq.top(); pq.pop();
        if(k%2) printf("%lld\n", p.first);

        int i = p.second;
        cnt[i]++;

        if(cnt[i] == n) continue;

        ll MIN = 0, MAX = 2e9, ANS = 2e9;
        while(MIN <= MAX){
            ll MID = (MIN + MAX) / 2;
            if(sum(arr[i].first - MID, arr[i].first + MID, arr[i].second - MID, arr[i].second + MID) > cnt[i]){
                ANS = MID;
                MAX = MID-1;
            }
            else MIN = MID+1;
        }
        minDist[i] = ANS;
        pq.push(make_pair(ANS, i));
    }

    assert(nodeCnt <= 100000);
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%lld %lld", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8330 ms 3956 KB Output is correct
2 Correct 8032 ms 3956 KB Output is correct
3 Incorrect 6035 ms 3692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8330 ms 3956 KB Output is correct
2 Correct 8032 ms 3956 KB Output is correct
3 Incorrect 6035 ms 3692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8330 ms 3956 KB Output is correct
2 Correct 8032 ms 3956 KB Output is correct
3 Incorrect 6035 ms 3692 KB Output isn't correct
4 Halted 0 ms 0 KB -