Submission #386573

#	Time	Username	Problem	Language	Result	Execution time	Memory
386573		limabeans	Road Construction (JOI21_road_construction)	C++17	0 / 100	10024 ms	4460 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;




ll dist(pair<ll,ll> a, pair<ll,ll> b) {
    return abs(a.first-b.first)+abs(a.second-b.second);
}

int n,k;
vector<pair<int,int>> a;



// contrib: -x + (y)
// (contrib, idx)

struct Yset {
    multiset<ll> contrib;
    set<pair<ll,int>> byY;

    vector<ll> get(int k) {
	vector<ll> a;
	for (auto iter=contrib.rbegin(); iter!=contrib.rend() && k>0; ++iter, k--) {
	    a.push_back(*iter);
	}
	return a;
    }
};


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

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

    assert(k<=10);
    
    for (int i=0; i<n; i++) {
	cin>>a[i].first>>a[i].second;
    }

    sort(a.begin(), a.end());

    multiset<ll> ans;


    auto insert = [&](ll val) {
	ans.insert(val);
	while ((int)ans.size() > k) {
	    ans.erase(--ans.end());
	}
    };

    Yset above, below;
    
    for (int i=0; i<n; i++) {
	auto p = a[i];
	ll x = p.first;
	ll y = p.second;
	
	while (!above.byY.empty() && above.byY.begin()->first < y) {
	    auto cur = *above.byY.begin();
	    above.byY.erase(above.byY.begin());
	    int at = cur.second;
	    ll oldContrib = -a[at].first + a[at].second;
	    above.contrib.erase(above.contrib.find(oldContrib));
	    ll newContrib = -a[at].first - a[at].second;

	    below.byY.insert({a[at].second, at});
	    below.contrib.insert(newContrib);
	}

	while (!below.byY.empty() && below.byY.rbegin()->first > y) {
	    auto cur = *below.byY.rbegin();
	    below.byY.erase(--below.byY.end());
	    int at = cur.second;
	    ll oldContrib = -a[at].first - a[at].second;
	    below.contrib.erase(below.contrib.find(oldContrib));
	    ll newContrib = -a[at].first + a[at].second;

	    above.byY.insert({a[at].second, at});
	    above.contrib.insert(newContrib);
	}

	for (auto val: above.get(k)) {
	    insert(val + x - y);
	}
	for (auto val: below.get(k)) {
	    insert(val + x + y);
	}

	below.contrib.insert(-x-y);
	below.byY.insert({y,i});
    }


    for (ll x: ans) {
	cout<<x<<"\n";
    }
    
    return 0;
}

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