Submission #1306546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306546		KhoaDuy	Road Construction (JOI21_road_construction)	C++20	0 / 100	223 ms	4556 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,k;
const int MAXN=2*1e5;
vector<pair<int,int>> v;
vector<int> bst;
int solve(int limit,bool trace){
    if(limit<=0){
        return -1;
    }
    int curr=0;
    set<pair<int,int>> se;
    int ptr=-1;
    for(int i=0;i<n;i++){
        while(ptr+1<i&&v[i].first-v[ptr+1].first>limit){
            ptr++;
            se.erase({v[ptr].second,ptr});
        }
        auto it=se.lower_bound({v[i].second-limit,0});
        for(;it!=se.end()&&(*it).first<=v[i].second+limit;it++){
            curr++;
            if(curr>=k){
                return curr;
            }
            if(trace){
                int idx=(*it).second;
                bst.push_back(max(abs(v[i].first-v[idx].first),(v[i].second-v[idx].second)));
            }
        }
        se.insert({v[i].second,i});
    }
    return curr;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen("input.txt","r")){
        freopen("input.txt","r",stdin);
    }
    cin >> n >> k;
    v.resize(n);
    for(int i=0;i<n;i++){
        cin >> v[i].first >> v[i].second;
        v[i]={v[i].first-v[i].second,v[i].first+v[i].second};
    }
    sort(v.begin(),v.end());
    int low=1,high=2e9;
    low--,high++;
    while(high-low>1){
        int mid=((high-low)>>1)+low;
        if(solve(mid,false)>=k){
            high=mid;
        }
        else{
            low=mid;
        }
    }
    solve(low,true);
    while(bst.size()<k){
        bst.push_back(high);
    }
    sort(bst.begin(),bst.end());
    for(int i=0;i<k;i++){
        cout << bst[i] << endl;
    }
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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