Submission #387048

#	Time	Username	Problem	Language	Result	Execution time	Memory
387048		keko37	Road Construction (JOI21_road_construction)	C++14	100 / 100	8023 ms	52704 KiB

road_construction

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 250005;
const int LOG = 18;

llint n, k;
llint x[MAXN], y[MAXN], sx[MAXN], sy[MAXN], fen[MAXN], ind[MAXN];
vector <llint> sazx, sazy, vx[MAXN], vy[MAXN], sol;

void ubaci (llint x, llint k) {
    for (x++; x < MAXN; x += x&-x) fen[x] += k;
}

llint upit (llint x) {
    llint res = 0;
    for (x++; x > 0; x -= x&-x) res += fen[x];
    return res;
}

llint kth (llint br) {
    llint pos = 0;
    for (int i = LOG - 1; i >= 0; i--) {
        if (pos + (1 << i) < MAXN && br > fen[pos + (1 << i)]) {
            pos += 1 << i;
            br -= fen[pos];
        }
    }
    return pos;
}

bool cmp (int i, int j) {
    return y[i] < y[j];
}

void sazmi () {
    for (int i = 1; i <= n; i++) {
        sazx.push_back(x[i]);
        sazy.push_back(y[i]);
    }
    sort(sazx.begin(), sazx.end());
    sort(sazy.begin(), sazy.end());
    sazx.erase(unique(sazx.begin(), sazx.end()), sazx.end());
    sazy.erase(unique(sazy.begin(), sazy.end()), sazy.end());
    for (int i = 1; i <= n; i++) {
        sx[i] = lower_bound(sazx.begin(), sazx.end(), x[i]) - sazx.begin();
        sy[i] = lower_bound(sazy.begin(), sazy.end(), y[i]) - sazy.begin();
        vx[sx[i]].push_back(i);
    }
    for (int i = 0; i < sazx.size(); i++) {
        sort(vx[i].begin(), vx[i].end(), cmp);
        for (auto j : vx[i]) {
            vy[sy[j]].push_back(j);
        }
    }
}

llint get_dist (int i, int j) {
    return max(abs(x[i] - x[j]), abs(y[i] - y[j]));
}

llint calc (llint len, bool flg) {
    llint res = 0;
    int p = 0;
    for (int i = 0; i < sazy.size(); i++) {
        ind[i] = 0;
    }
    for (int i = 0; i < sazx.size(); i++) {
        while (p < i && sazx[i] - sazx[p] > len) {
            for (auto j : vx[p]) {
                ubaci(sy[j], -1);
                ind[sy[j]]++;
            }
            p++;
        }
        for (auto j : vx[i]) {
            llint lo = lower_bound(sazy.begin(), sazy.end(), y[j] - len) - sazy.begin();
            llint hi = upper_bound(sazy.begin(), sazy.end(), y[j] + len) - sazy.begin() - 1;
            llint br_lo = upit(lo - 1);
            llint br_hi = upit(hi);
            res += br_hi - br_lo;
            if (flg == 1) {
                vector <llint> tmp;
                for (llint br = br_lo + 1; br <= br_hi; br++) {
                    tmp.push_back(kth(br));
                }
                tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
                for (auto h : tmp) {
                    for (int br = ind[h]; br < vy[h].size(); br++) {
                        int sus = vy[h][br];
                        if (x[sus] > x[j] || x[sus] == x[j] && y[sus] >= y[j]) break;
                        sol.push_back(get_dist(j, sus));
                    }
                }
            }
            ubaci(sy[j], 1);
        }
    }
    while (p < sazx.size()) {
        for (auto j : vx[p]) {
            ubaci(sy[j], -1);
        }
        p++;
    }
    return res;
}

llint get_len () {
    llint lo = 1, hi = 4e9 + 5;
    while (lo < hi) {
        llint mid = (lo + hi) / 2;
        if (calc(mid, 0) >= k) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> k;
    //n = 250000; k = 250000;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        //x[i] = uniform_int_distribution<int>(-1e9, 1e9)(rng);
        //y[i] = uniform_int_distribution<int>(-1e9, 1e9)(rng);
        int nx = x[i] - y[i];
        int ny = x[i] + y[i];
        x[i] = nx; y[i] = ny;
        //cout << "bla " << nx << " " << ny << endl;
    }
    sazmi();
    llint len = get_len();
    calc(len - 1, 1);
    sort(sol.begin(), sol.end());
    while (sol.size() < k) sol.push_back(len);
    for (auto x : sol) cout << x << '\n';
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'void sazmi()':
road_construction.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < sazx.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
road_construction.cpp: In function 'llint calc(llint, bool)':
road_construction.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < sazy.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
road_construction.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < sazx.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
road_construction.cpp:93:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     for (int br = ind[h]; br < vy[h].size(); br++) {
      |                                           ~~~^~~~~~~~~~~~~~
road_construction.cpp:95:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   95 |                         if (x[sus] > x[j] || x[sus] == x[j] && y[sus] >= y[j]) break;
      |                                              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:103:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     while (p < sazx.size()) {
      |            ~~^~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:144:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'llint' {aka 'long long int'} [-Wsign-compare]
  144 |     while (sol.size() < k) sol.push_back(len);
      |            ~~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35