oj.uz

답안 #921952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921952 2024-02-04T15:01:16 Z Darren0724 Road Construction (JOI21_road_construction) C++17
0 / 100
 3476 ms 2097152 KB 
#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=1e18;
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){
    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++;
        }
        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;
        ans.clear();
        (f(m)?r:l)=m;
    }
    ans.clear();
    f(l);
    while(ans.size()<k)ans.push_back(r);
    sort(all(ans));
    for(int j:ans){
        cout<<j<<'\n';
    }

    return 0;
}

Compilation message

road_construction.cpp:10:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int INF=1e18;
      |               ^~~~
road_construction.cpp: In function 'int f(int)':
road_construction.cpp:26:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3476 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 8468 KB Output is correct
2 Correct 276 ms 8644 KB Output is correct
3 Runtime error 1979 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 7532 KB Output is correct
2 Correct 246 ms 7372 KB Output is correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 7532 KB Output is correct
2 Correct 246 ms 7372 KB Output is correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3476 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3476 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -