Submission #386442

#	Time	Username	Problem	Language	Result	Execution time	Memory
386442		rocks03	Road Construction (JOI21_road_construction)	C++14	100 / 100	3961 ms	13028 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

class FenwickTree{
public:
    vector<int> fen;
    int bitsz;
    void build(int n){
        bitsz = n + 10;
        fen = vector<int>(bitsz, 0);
    }
    void add(int i, int k){
        ++i;
        for(; i < bitsz; i += (i & -i)) fen[i] += k;
    }
    int get(int i){
        ++i;
        int s = 0;
        for(; i; i -= (i & -i)) s += fen[i];
        return s;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
} bit;

const int MAXN = 3e5+100;
int N, K;
pll a[MAXN];
vector<ll> c;

bool check(ll mid){
    bit.build(N);
    int j = 0;
    ll ans = 0;
    rep(i, 0, N){
        while(a[i].ff - a[j].ff > mid){
            bit.add(a[j].ss, -1);
            j++;
        }
        int l = lower_bound(all(c), c[a[i].ss] - mid) - c.begin();
        int r = upper_bound(all(c), c[a[i].ss] + mid) - c.begin() - 1;
        ans += bit.get(l, r);
        bit.add(a[i].ss, +1);
    }
    return (ans >= K);
}

void print_answer(ll mid){
    vector<ll> answer;
    set<pii> s;
    int j = 0;
    rep(i, 0, N){
        while(a[i].ff - a[j].ff > mid){
            s.erase({a[j].ss, j});
            j++;
        }
        int l = lower_bound(all(c), c[a[i].ss] - mid) - c.begin();
        int r = upper_bound(all(c), c[a[i].ss] + mid) - c.begin() - 1;
        auto it = s.lower_bound({l, -1});
        while(it != s.end()){
            if((*it).ff > r) break;
            answer.pb(max(a[i].ff - a[(*it).ss].ff, abs(c[(*it).ff] - c[a[i].ss])));
            ++it;
        }
        s.insert({a[i].ss, i});
    }
    while(SZ(answer) < K) answer.pb(mid + 1);
    sort(all(answer));
    rep(i, 0, K) cout << answer[i] << "\n";
}

void solve(){
    cin >> N >> K;
    rep(i, 0, N){
        int x, y;
        cin >> x >> y;
        a[i] = {x - y, x + y};
        c.pb(x + y);
    }
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    rep(i, 0, N){
        a[i].ss = lower_bound(all(c), a[i].ss) - c.begin();
    }
    sort(a, a + N);
    ll l = 0, r = 1e11;
    while(r - l > 1){
        ll mid = (l + r) / 2;
        if(check(mid)){
            r = mid;
        } else{
            l = mid;
        }
    }
    print_answer(l);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

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