제출 #921959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921959		Darren0724	Road Construction (JOI21_road_construction)	C++17	0 / 100	2883 ms	2097152 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
int n,k;
vector<pair<int,int>> v;
vector<int> ans;
const int INF=1e9;
int calc(pair<int,int> a,pair<int,int> b){
    return max(abs(a.x-b.x),abs(a.y-b.y));
}
int f(int p){
    ans.clear();
    set<pair<int,int>> s;
    for(int i=0,j=0;i<n;i++){
        while(v[i].y-v[j].y>p){
            s.erase(v[j++]);
        }
        auto it=s.lower_bound({v[i].x-p,-INF});
        auto it1=s.upper_bound({v[i].x+p,INF});
        while(it!=it1){
            ans.push_back(calc(*it,v[i]));
            it++;
        }
        assert(ans.size()<=5000000);
        if(ans.size()>=k)return 1;
        s.insert(v[i]);
    }
    return 0;
}
int32_t main(){
    abcorz;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        v.push_back({a-b,a+b});
    }
    sort(all(v),[](pair<int,int> a,pair<int,int> b){return a.y<b.y;});
    int l=0,r=2e9;
    while(r-l>1){
        int m=(l+r)>>1;
        (f(m)?r:l)=m;
    }
    f(l);
    while(ans.size()<k)ans.push_back(r);
    sort(all(ans));
    for(int j:ans){
        cout<<j<<'\n';
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp: In function 'int f(int)':
road_construction.cpp:28:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |         if(ans.size()>=k)return 1;
      |            ~~~~~~~~~~^~~
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while(ans.size()<k)ans.push_back(r);
      |           ~~~~~~~~~~^~

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