oj.uz

Submission #386573

# Submission time Handle Problem Language Result Execution time Memory
386573 2021-04-06T22:52:22 Z limabeans Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 4460 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10024 ms 3996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10024 ms 3996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -