Submission #589267

#	Time	Username	Problem	Language	Result	Execution time	Memory
589267		Peti	Road Construction (JOI21_road_construction)	C++14	100 / 100	2132 ms	23232 KiB

road_construction

    #include <bits/stdc++.h>

    using namespace std;

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

    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, -(long long)5e9});
            //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:27:35: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |                     if(ret.size() > k) return ret;
      |                        ~~~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:57:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |             if(tmp.size() <= k)
      |                ~~~~~~~~~~~^~~~

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