oj.uz

Submission #389177

# Submission time Handle Problem Language Result Execution time Memory
389177 2021-04-13T20:10:50 Z couplefire Road Construction (JOI21_road_construction) C++17
6 / 100
 2893 ms 48956 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 250000
#define INF 1000000000000000009ll
#define ll long long

int n, k;
vector<ll> ans;
set<pair<ll, ll>> st;
map<ll, vector<ll>> mp;

bool check(ll mid){
    ans.clear();
    st.clear();
    for(auto &i : mp){
        vector<ll> &v = i.second;
        ll x = i.first;
        for(auto &y : v){
            auto it = st.lower_bound({y-mid, -INF});
            while(it != st.end() && (*it).first <= y+mid){
                ans.push_back(max(abs((*it).first-y),x-(*it).second));
                if((int)ans.size() > k) return 0;
                it = next(it);
            }
            st.insert({y, x});
        }
        if(!mp.count(x-mid)) continue;
        vector<ll> &tmp = mp[x-mid];
        for(auto &y : tmp) st.erase({y, x-mid});
    }
    return 1;
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i<n; i++){
        ll a, b; cin >> a >> b;
        mp[a+b].push_back(a-b);
    }
    for(auto &x : mp) sort(x.second.begin(), x.second.end());
    ll lo = 1, hi = 4000000009;
    while(lo < hi){
        ll mid = lo+(hi-lo+1)/2;
        if(check(mid)) lo = mid;
        else hi = mid-1;
    }
    check(lo);
    sort(ans.begin(), ans.end());
    for(int i = 0; i<k; i++){
        if(i < (int)ans.size()) cout << ans[i] << endl;
        else cout << lo+1 << endl;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2893 ms 48956 KB Output is correct
2 Correct 2859 ms 48880 KB Output is correct
3 Correct 502 ms 5104 KB Output is correct
4 Correct 2460 ms 48748 KB Output is correct
5 Correct 2546 ms 48852 KB Output is correct
6 Correct 2421 ms 48940 KB Output is correct
7 Correct 2196 ms 48288 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 547 ms 38140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 547 ms 38140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -