oj.uz

Submission #415786

# Submission time Handle Problem Language Result Execution time Memory
415786 2021-06-01T13:59:24 Z 반딧불(#7611) Road Construction (JOI21_road_construction) C++17
100 / 100
 9307 ms 156536 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

struct Query {
    int mode; /// 0: �� �߰�, 1: ���� ����, 2: ���� ��
    ll x, y1, y2; int idx;
    Query(){}
    Query(int mode, ll x, ll y1, ll y2, int idx): mode(mode), x(x), y1(y1), y2(y2), idx(idx){}

    bool operator<(const Query &r)const{
        if(x != r.x) return x<r.x;
        return mode < r.mode;
    }
};

struct Fenwick {
    int n;
    int tree[250002];

    void init(){
        memset(tree, 0, sizeof(tree));
    }

    void add(int x, int y){
        x++;
        while(x <= n){
            tree[x] += y;
            x += x&-x;
        }
    }

    int sum(int x){
        x++;
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        return sum(r) - sum(l-1);
    }
} tree;

struct segTree{
    vector<pair<int, ll> > tree[1000002];

    void add(int i, int l, int r, int x, int arg1, ll arg2){
        tree[i].push_back(make_pair(arg1, arg2));
        if(l==r) return;
        int m = (l+r)>>1;
        if(x<=m) add(i*2, l, m, x, arg1, arg2);
        else add(i*2+1, m+1, r, x, arg1, arg2);
    }

    void addAns(int i, int l, int r, int s, int e, ll lim, vector<int> &tVec){
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            auto it = tree[i].rbegin();
            while(it != tree[i].rend() && it->second >= lim){
                tVec.push_back(it->first);
                ++it;
            }
            return;
        }
        int m = (l+r)>>1;
        addAns(i*2, l, m, s, e, lim, tVec);
        addAns(i*2+1, m+1, r, s, e, lim, tVec);
    }
} tree2;

int n, k;
vector<ll> yVal;

pair<ll, ll> arr[250002];
int tyloc[250002];

ll totalMin;
vector<ll> ans;

int main(){
    scanf("%d %d", &n, &k);
//    n = 250000, k = 250000;
    tree.n = n;
    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());

    for(int i=1; i<=n; i++){
        tyloc[i] = lower_bound(yVal.begin(), yVal.end(), arr[i].second) - yVal.begin();
    }

    {
        ll MIN = 0, MAX = 1e10, ANS = 1e10;
        while(MIN <= MAX){
            ll MID = (MIN + MAX) / 2;
            ll sum = -n;
            tree.init();
            vector<Query> vec;
            for(int i=1; i<=n; i++){
                int y2 = upper_bound(yVal.begin(), yVal.end(), arr[i].second + MID) - yVal.begin() - 1;
                int y1 = lower_bound(yVal.begin(), yVal.end(), arr[i].second - MID) - yVal.begin();
                vec.push_back(Query(0, arr[i].first, tyloc[i], tyloc[i], i));
                vec.push_back(Query(1, arr[i].first - MID - 1, y1, y2, i));
                vec.push_back(Query(2, arr[i].first + MID, y1, y2, i));
            }
            sort(vec.begin(), vec.end());

            for(Query query: vec){
                if(query.mode == 0) tree.add(query.y1, 1);
                else if(query.mode == 1) sum -= tree.sum(query.y1, query.y2);
                else sum += tree.sum(query.y1, query.y2);
            }

            if(sum >= k*2){
                ANS = MID;
                MAX = MID-1;
            }
            else MIN = MID+1;
        }
        totalMin = ANS;
    }

    totalMin--;
    vector<Query> vec;
    for(int i=1; i<=n; i++){
        int y2 = upper_bound(yVal.begin(), yVal.end(), arr[i].second + totalMin) - yVal.begin() - 1;
        int y1 = lower_bound(yVal.begin(), yVal.end(), arr[i].second - totalMin) - yVal.begin();
        vec.push_back(Query(0, arr[i].first, tyloc[i], tyloc[i], i));
        vec.push_back(Query(2, arr[i].first + totalMin, y1, y2, i));
    }
    sort(vec.begin(), vec.end());

    for(Query query: vec){
        if(query.mode == 0){
            tree2.add(1, 0, n, query.y1, query.idx, query.x);
        }
        else{
            vector<int> tVec;
            tree2.addAns(1, 0, n, query.y1, query.y2, arr[query.idx].first - totalMin, tVec);
            for(auto x: tVec){
                if(x <= query.idx) continue;
                ans.push_back(max(abs(arr[query.idx].first - arr[x].first), abs(arr[query.idx].second - arr[x].second)));
            }
        }
    }

    sort(ans.begin(), ans.end());
    while(ans.size() < k) ans.push_back(totalMin + 1);

    for(auto x: ans) printf("%lld\n", x);
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:166:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  166 |     while(ans.size() < k) ans.push_back(totalMin + 1);
      |           ~~~~~~~~~~~^~~
road_construction.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%lld %lld", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29556 KB Output is correct
2 Correct 100 ms 29584 KB Output is correct
3 Correct 98 ms 29760 KB Output is correct
4 Correct 96 ms 29776 KB Output is correct
5 Correct 92 ms 28564 KB Output is correct
6 Correct 37 ms 25080 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6381 ms 138804 KB Output is correct
2 Correct 6447 ms 138868 KB Output is correct
3 Correct 86 ms 29564 KB Output is correct
4 Correct 6389 ms 138688 KB Output is correct
5 Correct 6036 ms 138900 KB Output is correct
6 Correct 5979 ms 138924 KB Output is correct
7 Correct 5873 ms 138224 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8093 ms 135612 KB Output is correct
2 Correct 8689 ms 135660 KB Output is correct
3 Correct 20 ms 24652 KB Output is correct
4 Correct 5872 ms 135688 KB Output is correct
5 Correct 4941 ms 136000 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8093 ms 135612 KB Output is correct
2 Correct 8689 ms 135660 KB Output is correct
3 Correct 20 ms 24652 KB Output is correct
4 Correct 5872 ms 135688 KB Output is correct
5 Correct 4941 ms 136000 KB Output is correct
6 Correct 8216 ms 135612 KB Output is correct
7 Correct 8575 ms 135616 KB Output is correct
8 Correct 21 ms 24652 KB Output is correct
9 Correct 24 ms 24712 KB Output is correct
10 Correct 8872 ms 155116 KB Output is correct
11 Correct 6188 ms 135696 KB Output is correct
12 Correct 5136 ms 136348 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29556 KB Output is correct
2 Correct 100 ms 29584 KB Output is correct
3 Correct 98 ms 29760 KB Output is correct
4 Correct 96 ms 29776 KB Output is correct
5 Correct 92 ms 28564 KB Output is correct
6 Correct 37 ms 25080 KB Output is correct
7 Correct 3346 ms 75548 KB Output is correct
8 Correct 3410 ms 75608 KB Output is correct
9 Correct 88 ms 29800 KB Output is correct
10 Correct 3410 ms 72344 KB Output is correct
11 Correct 3215 ms 74056 KB Output is correct
12 Correct 2141 ms 74252 KB Output is correct
13 Correct 2242 ms 72100 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29556 KB Output is correct
2 Correct 100 ms 29584 KB Output is correct
3 Correct 98 ms 29760 KB Output is correct
4 Correct 96 ms 29776 KB Output is correct
5 Correct 92 ms 28564 KB Output is correct
6 Correct 37 ms 25080 KB Output is correct
7 Correct 6381 ms 138804 KB Output is correct
8 Correct 6447 ms 138868 KB Output is correct
9 Correct 86 ms 29564 KB Output is correct
10 Correct 6389 ms 138688 KB Output is correct
11 Correct 6036 ms 138900 KB Output is correct
12 Correct 5979 ms 138924 KB Output is correct
13 Correct 5873 ms 138224 KB Output is correct
14 Correct 8093 ms 135612 KB Output is correct
15 Correct 8689 ms 135660 KB Output is correct
16 Correct 20 ms 24652 KB Output is correct
17 Correct 5872 ms 135688 KB Output is correct
18 Correct 4941 ms 136000 KB Output is correct
19 Correct 8216 ms 135612 KB Output is correct
20 Correct 8575 ms 135616 KB Output is correct
21 Correct 21 ms 24652 KB Output is correct
22 Correct 24 ms 24712 KB Output is correct
23 Correct 8872 ms 155116 KB Output is correct
24 Correct 6188 ms 135696 KB Output is correct
25 Correct 5136 ms 136348 KB Output is correct
26 Correct 3346 ms 75548 KB Output is correct
27 Correct 3410 ms 75608 KB Output is correct
28 Correct 88 ms 29800 KB Output is correct
29 Correct 3410 ms 72344 KB Output is correct
30 Correct 3215 ms 74056 KB Output is correct
31 Correct 2141 ms 74252 KB Output is correct
32 Correct 2242 ms 72100 KB Output is correct
33 Correct 9208 ms 139676 KB Output is correct
34 Correct 9307 ms 139760 KB Output is correct
35 Correct 8730 ms 156536 KB Output is correct
36 Correct 5099 ms 135048 KB Output is correct
37 Correct 4983 ms 135304 KB Output is correct
38 Correct 5444 ms 141448 KB Output is correct