Submission #1209444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209444		Tyx2019	Road Construction (JOI21_road_construction)	C++20	100 / 100	4006 ms	43756 KiB

road_construction

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int mx = 2e9 + 5;
vector<pair<int, int>> V;
#define debug(x) if(0) cout << #x << " is " << x << endl;
int N, K;
vector<int> myfriends;
bool chk(int dist, bool walao = false){
    debug(walao)
    set<int> lolz;
    for(auto i:V){
        lolz.insert(i.first+dist);
    }
    int cnt = 0;
    int cur = 0;
    int backcur = 0;
    int worstcur = 0;
    multiset<pair<int, int>> dudes;
    for(auto i:lolz){
        while(cur != V.size() && V[cur].first <= i){
            dudes.insert({V[cur].second, V[cur].first});
            if(V[cur].first == 2 && V[cur].second == 2){
                debug("hi")
            }
            cur++;
        }
        while(worstcur != V.size() && V[worstcur].first < i - 2 * dist){
            dudes.erase(dudes.find({V[worstcur].second, V[worstcur].first}));
            if(V[worstcur].first == 2 && V[worstcur].second == 2){
                debug("hi")
            }
            worstcur++;
        }
        while(backcur != V.size() && V[backcur].first == i - dist){
            int l = V[backcur].second - dist;
            int r = V[backcur].second + dist;
            auto it = dudes.lower_bound({l, -2*mx});
            while(it != dudes.end() && (*it).first <= r){
                int x1 = V[backcur].first;
                int y1 = V[backcur].second;
                int x2 = (*it).second;
                int y2 = (*it).first;
    
                assert(max(abs(x1-x2), abs(y1-y2)) <= dist);
                if(walao){
                    if(x1 == 2 && y1 == 0){
                        debug(x2)
                        debug(y2)
                        if(y2 == 0){
                            auto it2 = it;
                            it2++;
                            debug((*it2).first);
                            debug((*it2).second)
                        }
                    }
                    myfriends.push_back(max(abs(x1-x2), abs(y1-y2)));
                }
                it++;
                cnt++;
                if(cnt >= K) return true;
            }
            backcur++;
        }
    }
    debug(cnt)
    debug(dist)
    return false;
}
main(){
    cin >> N >> K;
    K = 2 * K + N;
    int X[N], Y[N];
    for(int i=0;i<N;i++) cin >> X[i] >> Y[i];
    for(int i=0;i<N;i++){
        if(X[i] - Y[i] == 2 && X[i]+Y[i] == 2) debug("hola")
        V.push_back({X[i] - Y[i], X[i] + Y[i]});
    }
    sort(V.begin(), V.end());
    int l = 0;
    int r = 1e10;
    while(r > l){
        int m = (l + r) >> 1;
        if(chk(m)) r = m;
        else l = m + 1;
    }
    chk(l-1, true);
    sort(myfriends.begin(), myfriends.end());
    for(int i=N;i<myfriends.size();i+=2) cout << myfriends[i] << "\n";
    int res = (K - myfriends.size()) / 2;
    for(int i=0;i<res;i++) cout << l << " " << '\n';
    debug(myfriends.size())

}

Compilation message (stderr)

road_construction.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main(){
      | ^~~~

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