Submission #1166940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166940		mariaclara	Road Construction (JOI21_road_construction)	C++20	7 / 100	651 ms	13280 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[4*MAXN];
vector<pii> p;

void update(int node, int l, int r, int ind, pii val) {
    if(l == r) {
        seg[node] = max(val, seg[node]);
        return;
    }

    int mid = (l+r)/2;
    if(ind <= mid) update(2*node, l, mid, ind, val);
    else update(2*node+1, mid+1, r, ind, val);

    seg[node] = max(seg[2*node], seg[2*node+1]);
}

pii query(int node, int l, int r, int p, int q) { // flag = 1 pra mínimo e -1 pra máximo
    if(r < p or q < l) return {-2e9, -1};
    if(p <= l and r <= q) return seg[node];

    int mid = (l+r)/2;
    return max(query(2*node, l, mid, p, q),  query(2*node+1, mid+1, r, p, q));
}

int main() {

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

    vector<int> add, sub, ord(n);

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

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

    sort(all(p));
    fill(seg, seg+4*n+1, mk(-2e9, -1));

    ll R1 = 4e9;
    
    for(int i = 0; i < n; i++) {
        int ptr = lower_bound(all(add), p[i].fr + p[i].sc) - add.begin();
        auto [val,aux] = query(1, 0, n-1, ptr, n-1); // procurar o máximo x - y
        update(1, 0, n-1, ptr, {p[i].fr - p[i].sc, i});
        if(aux != -1) R1 = min(R1, p[i].fr - p[i].sc - (ll)val);
    }

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

    for(int i = 0; i < n; i++) {
        int ptr = lower_bound(all(sub), p[i].fr - p[i].sc) - sub.begin();
        auto [val,aux] = query(1, 0, n-1, ptr, n-1); // máximo x + y
        update(1, 0, n-1, ptr, {p[i].fr + p[i].sc, i});
        if(aux != -1) R1 = min(R1, p[i].fr + p[i].sc - (ll)val);
    }

    sort(all(ord), [](int a, int b){
        return mk(p[a].sc, p[a].fr) <= mk(p[b].sc, p[b].fr);
    });
    
    fill(seg, seg+4*n+1, mk(-2e9, -1));

    for(int i : ord) {
        int ptr = lower_bound(all(sub), p[i].fr - p[i].sc) - sub.begin();
        auto [val,aux] = query(1, 0, n-1, 0, ptr); // máximo x + y
        update(1, 0, n-1, ptr, {p[i].fr + p[i].sc, i});
        if(aux != -1) R1 = min(R1, p[i].fr + p[i].sc - (ll)val);
    }

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

    for(int i : ord) {
        int ptr = lower_bound(all(add), p[i].fr + p[i].sc) - add.begin();
        auto [val,aux] = query(1, 0, n-1, 0, ptr); // procurar o máximo x - y
        update(1, 0, n-1, ptr, {p[i].fr - p[i].sc, i});
        if(aux != -1) R1 = min(R1, p[i].fr - p[i].sc - (ll)val);
    }

    cout << R1 << "\n";
}

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