Submission #995532

#	Time	Username	Problem	Language	Result	Execution time	Memory
995532		vladilius	Road Construction (JOI21_road_construction)	C++17	5 / 100	10082 ms	174304 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<ll, 3>
const int inf = 1e9;

struct FT{
    vector<int> bit, ch;
    int n;
    void init(int ns){
        n = ns;
        bit.resize(n + 1);
    }
    void upd(int p, int k){
        while (p <= n){
            bit[p] += k;
            ch.pb(p);
            p |= (p + 1);
        }
    }
    int get(int v){
        v--;
        int out = 0;
        while (v > 0){
            out += bit[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
    void clear(){
        for (int i: ch) bit[i] = 0;
        ch.clear();
    }
};

struct TDC{
    struct data{
        int t, x, y, k;
    };
    vector<data> qs;
    FT T;
    TDC(int nn){
        T.init(nn);
    }
    void add_p(int x, int y){
        qs.pb({1, x, y});
    }
    void add_q(int x1, int x2, int y1, int y2){ // x є [x1, x2], y є [y1, y2]
        if (x1 > x2 || y1 > y2) return;
        qs.pb({0, x2 + 1, y2 + 1, 1});
        qs.pb({0, x1, y1, 1});
        qs.pb({0, x1, y2 + 1, -1});
        qs.pb({0, x2 + 1, y1, -1});
    }
    ll solve(int l, int r){
        if (l == r) return 0;
        int m = (l + r) / 2;
        ll sum = 0;
        vector<data> lf, rt;
        for (int i = l; i <= m; i++){
            if (qs[i].t != 0){
                lf.pb(qs[i]);
            }
        }
        for (int i = m + 1; i <= r; i++){
            if (!qs[i].t){
                rt.pb(qs[i]);
            }
        }
        
        auto cmp = [&](data& a, data& b){
            return a.x < b.x;
        };
        
        sort(lf.begin(), lf.end(), cmp);
        sort(rt.begin(), rt.end(), cmp);
        
        int i = 0, j = 0;
        while (j < rt.size()){
            while (i < lf.size() && lf[i].x < rt[j].x){
                T.upd(lf[i].y, lf[i].t);
                i++;
            }
            sum += rt[j].k * T.get(rt[j].y);
            j++;
        }
        
        T.clear();
        
        return sum + solve(l, m) + solve(m + 1, r);
    }
    ll solve(){
        ll out = solve(0, (int) qs.size() - 1);
        qs.clear();
        return out;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k; cin>>n>>k;
    vector<int> x(n + 1), y(n + 1), all;
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>y[i];
        all.pb(x[i]);
        all.pb(y[i]);
    }
    sort(all.begin(), all.end());
    int i = 0, cnt = 0;
    map<int, int> mp;
    while (i < all.size()){
        int j = i;
        while (j < all.size() && all[i] == all[j]) j++;
        mp[all[i]] = ++cnt;
        i = j;
    }
    vector<int> xp(n + 1), yp(n + 1);
    for (int i = 1; i <= n; i++){
        xp[i] = mp[x[i]];
        yp[i] = mp[y[i]];
    }
    
    TDC T(cnt);
    auto count = [&](ll d){ // #(1 <= i < j <= n) : abs(xi - xj) + abs(yi - yj) <= d
        ll out = -n;
        
        auto cmp = [&](arr3& a, arr3& b){
            if (a[0] == b[0]){
                return a[2] < b[2];
            }
            return a[0] > b[0];
        };
        
        // xi >= xj, yi >= yj: xi - xj + yi - yj <= d <-> xi + yi - d <= xj + yj
        
        vector<arr3> st;
        for (int i = 1; i <= n; i++){
            st.pb({x[i] + y[i], i, 0});
            st.pb({x[i] + y[i] - d, i, 1});
        }
        sort(st.begin(), st.end(), cmp);
        for (auto p: st){
            if (!p[2]){
                T.add_p(xp[p[1]], yp[p[1]]);
                continue;
            }
            T.add_q(1, xp[p[1]], 1, yp[p[1]]);
        }
        out += T.solve();
        
        // xi >= xj, yi < yj: xi - xj + yj - yi <= d <-> xi - yi - d <= xj - yj
        
        st.clear();
        for (int i = 1; i <= n; i++){
            st.pb({x[i] - y[i], i, 0});
            st.pb({x[i] - y[i] - d, i, 1});
        }
        sort(st.begin(), st.end(), cmp);
        for (auto p: st){
            if (!p[2]){
                T.add_p(xp[p[1]], yp[p[1]]);
                continue;
            }
            T.add_q(1, xp[p[1]], yp[p[1]] + 1, cnt);
        }
        out += T.solve();
        
        
        // xi < xj, yi >= yj: xj - xi + yi - yj <= d <-> yi - xi - d <= yj - xj
        
        st.clear();
        for (int i = 1; i <= n; i++){
            st.pb({y[i] - x[i], i, 0});
            st.pb({y[i] - x[i] - d, i, 1});
        }
        sort(st.begin(), st.end(), cmp);
        for (auto p: st){
            if (!p[2]){
                T.add_p(xp[p[1]], yp[p[1]]);
                continue;
            }
            T.add_q(xp[p[1]] + 1, cnt, 1, yp[p[1]]);
        }
        out += T.solve();
        
        // xi < xj, yi < yj: xj - xi + yj - yi <= d <-> -(xi + yi + d) <= -(xj + yj)
        
        st.clear();
        for (int i = 1; i <= n; i++){
            st.pb({-(x[i] + y[i]), i, 0});
            st.pb({-(x[i] + y[i] + d), i, 1});
        }
        sort(st.begin(), st.end(), cmp);
        for (auto p: st){
            if (!p[2]){
                T.add_p(xp[p[1]], yp[p[1]]);
                continue;
            }
            T.add_q(xp[p[1]] + 1, cnt, yp[p[1]] + 1, cnt);
        }
        out += T.solve();
        
        return out / 2;
    };

    ll l = 0, r = 4LL * inf;
    while (l + 1 < r){
        ll m = (l + r) / 2, g = count(m);
        if (g < k){
            l = m + 1;
        }
        else {
            if (g < 3e6) break;
            r = m;
        }
    }
    // find all pairs with MHD <= r
    vector<pll> p(n + 1);
    for (int i = 1; i <= n; i++){
        p[i] = {x[i], y[i]};
    }
    sort(p.begin() + 1, p.end());
    multiset<pll> st;
    vector<ll> dist;
    int j = 1;
    for (int i = 1; i <= n; i++){
        while (j < i && (p[i].ff - p[j].ff) > r){
            st.erase(st.find({p[j].ss, p[j].ff}));
            j++;
        }
        auto it = st.lower_bound({p[i].ss - r, -inf});
        ll R = p[i].ss + r;
        while (it != st.end() && (*it).ff <= R){
            ll d = abs(p[i].ff - (*it).ss) + abs(p[i].ss - (*it).ff);
            if (d <= r){
                dist.pb(d);
            }
            it++;
        }
        st.insert({p[i].ss, p[i].ff});
    }
    
    sort(dist.begin(), dist.end());
    for (int i = 0; i < k; i++){
        cout<<dist[i]<<"\n";
    }
}

// Looks like O(n * log^3(n) + ?) is very fast!
// No :( ???

Compilation message (stderr)

road_construction.cpp: In member function 'll TDC::solve(int, int)':
road_construction.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TDC::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (j < rt.size()){
      |                ~~^~~~~~~~~~~
road_construction.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TDC::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while (i < lf.size() && lf[i].x < rt[j].x){
      |                    ~~^~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     while (i < all.size()){
      |            ~~^~~~~~~~~~~~
road_construction.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         while (j < all.size() && all[i] == all[j]) j++;
      |                ~~^~~~~~~~~~~~

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