Submission #1116669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116669		_callmelucian	Road Construction (JOI21_road_construction)	C++14	100 / 100	7033 ms	19812 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 250003;
vector<ll> cmpSum, cmpDiff;
pl a[mn];
ll n;

struct BIT {
    vector<int> tr;
    BIT (int sz) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int k, int val) {
        for (; k < tr.size(); k += p(k)) tr[k] += val;
    }

    int preSum (int k, int ans = 0) {
        for (; k; k -= p(k)) ans += tr[k];
        return ans;
    }

    void refresh() { fill(all(tr), 0); }
} treeSum(mn), treeDiff(mn);

int getSum (ll targ) {
    return lower_bound(all(cmpSum), targ) - cmpSum.begin() + 1;
}

int getDiff (ll targ) {
    return lower_bound(all(cmpDiff), targ) - cmpDiff.begin() + 1;
}

int pointSum (int i) {
    ll x, y; tie(x, y) = a[i];
    return lower_bound(all(cmpSum), x + y) - cmpSum.begin() + 1;
}

int pointDiff (int i) {
    ll x, y; tie(x, y) = a[i];
    return lower_bound(all(cmpDiff), x - y) - cmpDiff.begin() + 1;
}

ll countClose (ll ub) {
    ll cnt = 0;
    treeSum.refresh(), treeDiff.refresh();
    for (int L = 0, R = 0; R < n; R++) {
        treeSum.update(pointSum(R), 1);
        treeDiff.update(pointDiff(R), 1);
        while (a[R].first - a[L].first > ub) {
            treeSum.update(pointSum(L), -1);
            treeDiff.update(pointDiff(L), -1);
            L++;
        }
        cnt += L;

        ll x, y; tie(x, y) = a[R];
        cnt += treeSum.preSum(getSum(x + y - ub) - 1);
        cnt += treeDiff.preSum(getDiff(x - y - ub) - 1);
    }
    return n * (n - 1) / 2 - cnt;
}

ll distance (ll x, ll y, ll i, ll j) {
    return abs(x - i) + abs(y - j);
}

void getPoints (ll ub, ll k, vector<ll> &ans) {
    set<pl> s;
    for (int L = 0, R = 0; R < n; R++) {
        ll x, y; tie(x, y) = a[R];
        s.emplace(y, x);

        while (a[R].first - a[L].first > ub) {
            ll x, y; tie(x, y) = a[L++];
            s.erase(make_pair(y, x));
        }

        for (auto it = s.lower_bound(make_pair(y - ub, 0)); it != s.end() && it->first <= y + ub; it++) {
            ll cur = distance(it->second, it->first, x, y);
            if (0 < cur && cur <= ub) ans.push_back(cur);
            if (ans.size() == k) break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll k; cin >> n >> k;
    for (int i = 0; i < n; i++) {
        ll x, y; cin >> x >> y;
        cmpSum.push_back(x + y), cmpDiff.push_back(x - y);
        a[i] = {x, y};
    }
    sort(a, a + n), sort(all(cmpSum)), sort(all(cmpDiff));
    filter(cmpSum), filter(cmpDiff);

    ll ans = 0, save = 0;
    for (ll mask = 1LL << 31; mask > 0; mask >>= 1) {
        ll cur = countClose(ans | mask);
        if (cur < k) ans |= mask, save = cur;
    }

    vector<ll> vec;
    getPoints(ans, save, vec);
    sort(all(vec));

    for (ll u : vec) cout << u << "\n";
    for (int i = 0; i < k - save; i++) cout << ans + 1 << "\n";

    return 0;
}

Compilation message (stderr)

road_construction.cpp: In member function 'void BIT::update(int, int)':
road_construction.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (; k < tr.size(); k += p(k)) tr[k] += val;
      |                ~~^~~~~~~~~~~
road_construction.cpp: In function 'void getPoints(ll, ll, std::vector<long long int>&)':
road_construction.cpp:92:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   92 |             if (ans.size() == k) break;
      |                 ~~~~~~~~~~~^~~~

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