oj.uz

Submission #415742

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

using namespace std;

typedef long long ll;

int n, k;
int l[5000000], r[5000000];
int s[5000000], e[5000000];
int val[5000000];
int nodeCnt = 0;

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

vector<ll> yVal;

int newNode(int _s, int _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, int x){
    if(s[i] == e[i]){
        val[i]++;
        return;
    }
    int m = (s[i] + e[i]) / 2;
    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 sumCnt = 0;
int sum(int i, int rs, int re){
    sumCnt++;
    if(rs <= s[i] && e[i] <= re) return val[i];
    int m = (s[i] + e[i]) / 2;
    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(int x, int y){
    if(locList[rootCnt] != x){
        root[rootCnt+1] = newNode(0, n, 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;
    ye = upper_bound(yVal.begin(), yVal.end(), ye) - yVal.begin() - 1;
    ys = lower_bound(yVal.begin(), yVal.end(), ys) - yVal.begin();
    return sum(root[xe], ys, ye) - sum(root[xs], ys, ye);
}

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);
//    n = 1000, k = 250000;
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
//        arr[i].first = rand();
//        arr[i].second = rand();
        ll tx = arr[i].first, ty = arr[i].second;
        arr[i].first = tx + ty, arr[i].second = tx - ty;
        yVal.push_back(arr[i].second);
    }

    sort(arr+1, arr+n+1);
    sort(yVal.begin(), yVal.end());
    yVal.erase(unique(yVal.begin(), yVal.end()), yVal.end());

    locList[0] = -1e15;
    root[0] = newNode(0, n);
    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;
    int turnCnt = 0;
    while(k--){
        assert(!pq.empty());
        pair<ll, int> p = pq.top(); pq.pop();
        if(k%2) printf("%lld\n", p.first);
//        if(++turnCnt % 1000 == 0) printf("%d\n", turnCnt);

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

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

        ll MIN = 0, MAX = 1e10, ANS = 1e10;
        while(MIN <= MAX){
            ll MID = (MIN + MAX) / 2;
            sumCnt = 0;
            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;
//            printf("%d\n", sumCnt);
        }
        minDist[i] = ANS;
        pq.push(make_pair(ANS, i));
    }
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2712 ms 3304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8825 ms 108596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6185 ms 106588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6185 ms 106588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2712 ms 3304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2712 ms 3304 KB Output isn't correct
2 Halted 0 ms 0 KB -