oj.uz

Submission #921959

# Submission time Handle Problem Language Result Execution time Memory
921959 2024-02-04T15:04:58 Z Darren0724 Road Construction (JOI21_road_construction) C++17
0 / 100
 2883 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=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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 2883 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 5440 KB Output is correct
2 Correct 324 ms 5604 KB Output is correct
3 Runtime error 1754 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 2512 KB Output is correct
2 Correct 277 ms 2452 KB Output is correct
3 Runtime error 1 ms 344 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 2512 KB Output is correct
2 Correct 277 ms 2452 KB Output is correct
3 Runtime error 1 ms 344 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2883 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 2883 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -