Submission #1110360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110360		onbert	Road Construction (JOI21_road_construction)	C++17	38 / 100	10061 ms	963292 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 1e10;
struct pt {
    int x, y, lcnt, rcnt, cur, id;
    bool operator < (const pt &b) const {
        return x + y < b.x + b.y;
    }
};
struct thing {
    int id, plus, l, r, delta;
    bool operator < (const thing &b) const {
        return plus < b.plus;
    }
};
int n, k;

int fen[maxn];
vector<int> sub;
int dcl(int x) {return lower_bound(sub.begin(), sub.end(), x) - sub.begin();}
int dcr(int x) {return upper_bound(sub.begin(), sub.end(), x) - sub.begin() - 1;}

void update(int id, int len) {
    while (id <= len) {
        fen[id]++;
        id += (id & -id);
    }
}
int sum(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

void cunt(vector<pt> &vec, int dist, int sgn) {
    int sz = vec.size();
    sub = {-INF};
    for (auto &[x, y, lcnt, rcnt, cur, id]:vec) sub.push_back(x - y);
    sort(sub.begin(), sub.end()); sub.erase(unique(sub.begin(), sub.end()), sub.end());
    int len = sub.size();
    for (int i=0;i<=len;i++) fen[i] = 0;
    vector<thing> qry;
    for (int i=0;i<sz;i++) {
        auto [x, y, lcnt, rcnt, cur, id] = vec[i];
        qry.push_back({i, x + y - dist - 1, dcl(x - y - dist), dcr(x - y + dist), -1});
        qry.push_back({i, x + y + dist, dcl(x - y - dist), dcr(x - y + dist), 1});
    }
    sort(qry.begin(), qry.end());
    int pter = 0;
    for (int i=0;i<sz;i++) {
        // cout << i << " " << pter << endl;
        auto [x, y, lcnt, rcnt, cur, id] = vec[i];
        while (pter < sz*2 && qry[pter].plus < x + y) {
            vec[qry[pter].id].cur += (sum(qry[pter].r) - sum(qry[pter].l - 1)) * qry[pter].delta * sgn;
            pter++;
        }
        update(dcl(x - y), len);
    }
    while (pter < sz*2) {
        vec[qry[pter].id].cur += (sum(qry[pter].r) - sum(qry[pter].l - 1)) * qry[pter].delta * sgn;
        pter++;
    }
}

vector<pair<int,int>> cnt[maxn];
void solve(int l, int r, vector<pt> &vec) {
    if (l==r) return;
    // if (l==1 && r==1) for (auto [x, y, lcnt, rcnt, cur]:vec) cout << x << " " << y << " " << lcnt << " " << rcnt << endl;
    // if (l==1 && r==1) exit(0);
    int mid = (l+r)/2;
    cunt(vec, mid, 1);
    cunt(vec, l-1, -1);
    vector<pt> L, R;
    int total = 0;
    // if (mid == 4) cout << vec.size() << " " << l << " " << r << endl;
    // cout << l << " " << mid << " " << r << " " << vec.size() << endl;
    for (auto &[x, y, lcnt, rcnt, cur, id]:vec) {
        cur += lcnt;
        cnt[id].push_back({mid, cur});
        // if (id == 0) cout << "test " << l << " " << mid << " " << r << " " << cur << endl;
        total += cur;
        if (cur != lcnt) L.push_back({x, y, lcnt, cur, 0, id});
        if (cur != rcnt) R.push_back({x, y, cur, rcnt, 0, id});
    }
    // cout << "L\n";
    // for (auto [x, y, lcnt, rcnt, cur]:L) cout << x << " " << y << " " << lcnt << " " << rcnt << " " << cur << endl;
    // cout << "R\n";
    // for (auto [x, y, lcnt, rcnt, cur]:R) cout << x << " " << y << " " << lcnt << " " << rcnt << " " << cur << endl;
    if (L.size()) solve(l, mid, L);
    if (R.size() && total < 2*k) solve(mid+1, r, R);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    vector<pt> vec(n);
    for (auto &[x, y, lcnt, rcnt, cur, id]:vec) cin >> x >> y, lcnt = 0, rcnt = n-1;
    sort(vec.begin(), vec.end());
    for (int i=0;i<n;i++) vec[i].id = i;
    // for (auto &[x, y, lcnt, rcnt, cur]:vec) cout << x << " " << y << " " << cur << endl;
    solve(1, INF, vec);

    map<int,int> mp;
    for (int i=0;i<n;i++) {
        sort(cnt[i].begin(), cnt[i].end());
        // cout << "test " << vec[i].x << " " << vec[i].y << endl;
        for (int j=0;j<cnt[i].size();j++) {
            bool kill = false;
            if (cnt[i][j].second == n-1) kill = true;
            int freq = cnt[i][j].second;
            if (j>0) freq -= cnt[i][j-1].second;
            mp[cnt[i][j].first] += freq;
            // cout << cnt[i][j].first << " " << freq << endl;
            if (kill) break;
        }
        // cout << "test " << vec[i].x << " " << vec[i].y << endl;
        // for (auto [dist, freq]:cnt[i]) if (dist<=12) cout << dist << " " << freq << endl;
    }
    int pos = 0;
    for (auto [dist, freq]:mp) {
        freq /= 2;
        for (int i=0;i<freq;i++) {
            pos++;
            cout << dist << '\n';
            if (pos == k) break;
        }
        if (pos == k) break;
    }
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:111:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int j=0;j<cnt[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~

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