oj.uz

Submission #415712

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

using namespace std;

typedef long long ll;

struct PST{
    struct Node{
        Node *l, *r;
        ll s, e;
        int created;
        int val;

        Node(){
            l = r = nullptr;
        }
        Node(ll s, ll e, int created): s(s), e(e), created(created){
//            printf("New node: %d %d %d\n", s, e, created);
            l = r = nullptr;
            val = 0;
        }
        Node* decent(int c){
            Node* ret = new Node(s, e, c);
            ret->val = val;
            ret->l = l, ret->r = r;
            return ret;
        }

        ~Node(){
            if(l && created == l->created) delete l;
            if(r && created == r->created) delete r;
        }

        void addPoint(int x){
            if(s==e){
                val++;
                return;
            }
            ll m = (s+e+INT_MAX+INT_MAX)/2-INT_MAX;
            if(x <= m){
                if(l && l->created == created){}
                else if(l) l = l->decent(created);
                else l = new Node(s, m, created);
                l->addPoint(x);
            }
            else{
                if(r && r->created == created){}
                else if(r) r = r->decent(created);
                else r = new Node(m+1, e, created);
                r->addPoint(x);
            }
            val = (l ? l->val : 0) + (r ? r->val : 0);
        }

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

    int sz;
    Node* root[250002];
    vector<ll> locList;

    PST(){
        sz = 0;
        locList.push_back(-1e10);
        root[0] = new Node(-2e9, 2e9, 0);
    }

    void deleteNodes(){
        for(int i=sz; i>=0; i--) delete root[i];
    }

    void addPoint(ll x, ll y){
        if(locList.back() != x){
            root[sz+1] = root[sz]->decent(sz);
            sz++;
            locList.push_back(x);
        }
        root[sz]->addPoint(y);
    }

    int sum(ll xs, ll xe, ll ys, ll ye){
        xe = upper_bound(locList.begin(), locList.end(), xe) - locList.begin() - 1;
        xs = lower_bound(locList.begin(), locList.end(), xs) - locList.begin() - 1;
        return root[xe]->sum(ys, ye) - root[xs]->sum(ys, ye);
    }
} tree;

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);

    for(int i=1; i<=n; i++){
        tree.addPoint(arr[i].first, arr[i].second);
    }

    for(int i=1; i<=n; i++){
        ll MIN = 0, MAX = 2e9, ANS = 2e9;
        cnt[i]++;
        while(MIN <= MAX){
            ll MID = (MIN + MAX) / 2;
            if(tree.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(tree.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));
    }
    tree.deleteNodes();
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7006 ms 4444 KB Output is correct
2 Correct 6797 ms 4672 KB Output is correct
3 Incorrect 5137 ms 4056 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 10130 ms 402000 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 10122 ms 400444 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 10122 ms 400444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7006 ms 4444 KB Output is correct
2 Correct 6797 ms 4672 KB Output is correct
3 Incorrect 5137 ms 4056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7006 ms 4444 KB Output is correct
2 Correct 6797 ms 4672 KB Output is correct
3 Incorrect 5137 ms 4056 KB Output isn't correct
4 Halted 0 ms 0 KB -