Submission #1176712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176712		mariaclara	Road Construction (JOI21_road_construction)	C++20	65 / 100	10092 ms	14460 KiB

road_construction

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 25e4+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first 
#define sc second 

int n, k;
pii seg[2*MAXN];
vector<pii> p, add, sub;
vector<int> ord;

void update(int ind, pii val) {
	seg[ind += n] = val;
	for (ind /= 2; ind; ind /= 2) seg[ind] = max(seg[2 * ind], seg[2 * ind + 1]);
}

pii query(int lo, int hi) {
	pii ra = {-2e9, -1}, rb = {-2e9, -1};
	for (lo += n, hi += n + 1; lo < hi; lo /= 2, hi /= 2) {
		if (lo & 1) ra = max(ra, seg[lo++]);
		if (hi & 1) rb = max(rb, seg[--hi]);
	}
	return max(ra, rb);
}

bool check(ll X, bool flag, vector<ll> &ans) {
    ans.clear();
    int cnt = 0;

    fill(seg, seg+2*n+1, mk(-2e9, -1));
    
    for(int i = 0; i < n; i++) {
        if(cnt == k) return 1;
        vector<int> re_add = {i};
        
        while(cnt < k) {
            int ptr = lower_bound(all(add), mk(p[i].fr + p[i].sc, 0)) - add.begin();
            auto [val,j] = query(ptr, n-1); // procurar o máximo x - y
            if(j == -1 or (ll)p[i].fr - (ll)p[i].sc - (ll)val > X) break;

            cnt++;
            if(flag) ans.pb((ll)p[i].fr - (ll)p[i].sc - (ll)val);
            re_add.pb(j);
            ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
            update(ptr, {-2e9, -1});
        }

        for(int j : re_add) {
            int ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
            update(ptr, {p[j].fr - p[j].sc, j});
        }
    }
    
    fill(seg, seg+2*n+1, mk(-2e9, -1));

    for(int i = 0; i < n; i++) {
        if(cnt == k) return 1;
        vector<int> re_add = {i};
        
        while(cnt < k) {
            int ptr = lower_bound(all(sub), mk(p[i].fr - p[i].sc, 0)) - sub.begin();
            auto [val,j] = query(ptr, n-1); // procurar o máximo x + y
            if(j == -1 or (ll)p[i].fr + (ll)p[i].sc - (ll)val > X) break;

            cnt++;
            if(flag) ans.pb((ll)p[i].fr + (ll)p[i].sc - (ll)val);
            re_add.pb(j);
            ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
            update(ptr, {-2e9, -1});
        }

        for(int j : re_add) {
            int ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
            update(ptr, {p[j].fr + p[j].sc, j});
        }
    }

    fill(seg, seg+2*n+1, mk(-2e9, -1));

    for(int i : ord) {
        if(cnt == k) return 1;
        vector<int> re_add = {i};
        
        while(cnt < k) {
            int ptr = lower_bound(all(sub), mk(p[i].fr - p[i].sc, 0)) - sub.begin();
            auto [val,j] = query(0, ptr - 1); // procurar o máximo x + y
            if(j == -1 or (ll)p[i].fr + (ll)p[i].sc - (ll)val > X) break;

            cnt++;
            if(flag) ans.pb((ll)p[i].fr + (ll)p[i].sc - (ll)val);
            re_add.pb(j);
            ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
            update(ptr, {-2e9, -1});
        }

        for(int j : re_add) {
            int ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
            update(ptr, {p[j].fr + p[j].sc, j});
        }
    }

    reverse(all(ord));
    fill(seg, seg+2*n+1, mk(-2e9, -1));

    for(int i : ord) {
        if(cnt == k) {
            reverse(all(ord));
            return 1;
        }
        vector<int> re_add = {i};
        
        while(cnt < k) {
            int ptr = lower_bound(all(add), mk(p[i].fr + p[i].sc, 0)) - add.begin();
            auto [val,j] = query(0, ptr - 1); // procurar o máximo x - y
            if(j == -1 or (ll)p[i].fr - (ll)p[i].sc - (ll)val > X) break;

            cnt++;
            if(flag) ans.pb((ll)p[i].fr - (ll)p[i].sc - (ll)val);
            re_add.pb(j);
            ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
            update(ptr, {-2e9, -1});
        }

        for(int j : re_add) {
            int ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
            update(ptr, {p[j].fr - p[j].sc, j});
        }
    }
    reverse(all(ord));

    if(cnt < k) return 0;
    return 1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    p.resize(n);

    ord.resize(n);

    for(int i = 0; i < n; i++) {
        cin >> p[i].fr >> p[i].sc;
        ord[i] = i;
    }

    sort(all(p));
    sort(all(ord), [](int a, int b){
        return mk(p[a].sc, p[a].fr) <= mk(p[b].sc, p[b].fr);
    });

    for(int i = 0; i < n; i++) {
        add.pb({p[i].fr + p[i].sc, i});
        sub.pb({p[i].fr - p[i].sc, i});
    }

    sort(all(add));
    sort(all(sub));

    ll l = 0, r = 4e9;
    vector<ll> ans;

    while(l <= r) {
        ll mid = (l+r)/2;
        if(check(mid, 0, ans)) r = mid-1;
        else l = mid+1;
    }

    check(r, 1, ans);
    while(sz(ans) < k) ans.pb(r+1);

    sort(all(ans));

    for(ll it : ans) cout << it << "\n";
} 

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