Submission #589266

#	Time	Username	Problem	Language	Result	Execution time	Memory
589266		Peti	Road Construction (JOI21_road_construction)	C++14	33 / 100	2289 ms	26272 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

struct pont{
    long long x, y;
    bool operator<(const pont &p) const{
        return x < p.x;
    }
};

vector<long long> megold(vector<pont> &v, int n, long long d, int k){
    //cout<<"start dist: "<<d<<'\n';
    set<pont> s;
    vector<long long> ret;
    for(pont p : v){
        auto it = s.lower_bound({p.x-d, 0});
        //cout<<"p: "<<p.x<<' '<<p.y<<"------------\n";
        while(it != s.end() && it->x <= p.x+d){
            //cout<<it->x<<' '<<it->y<<'\n';
            if(it->y < p.y-d){
                it++;
                s.erase(prev(it));
            } else{
                ret.push_back(max(abs(p.x - it->x), abs(p.y - it->y)));
                if(ret.size() > k) return ret;
                it++;
            }
        }
        s.insert(p);
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin>>n>>k;

    vector<pont> v(n);
    for(int i = 0; i < n; i++){
        long long x, y;
        cin>>x>>y;
        v[i].x = x+y;
        v[i].y = x-y;
    }

    sort(v.begin(), v.end(), [](pont a, pont b) -> bool{ return a.y < b.y; });

    long long l = 0, r = (long long)5e9;
    while(l+1ll < r){
        long long m = (l+r)/2;
        vector<long long> tmp = megold(v, n, m, k);
        if(tmp.size() <= k)
            l = m;
        else
            r = m;
    }

    vector<long long> ki = megold(v, n, l, k);
    ki.resize(k, l+1ll);

    sort(ki.begin(), ki.end());
    for(long long x : ki) cout<<x<<'\n';

    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'std::vector<long long int> megold(std::vector<pont>&, int, long long int, int)':
road_construction.cpp:26:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |                 if(ret.size() > k) return ret;
      |                    ~~~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:56:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         if(tmp.size() <= k)
      |            ~~~~~~~~~~~^~~~

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