oj.uz

Submission #589266

# Submission time Handle Problem Language Result Execution time Memory
589266 2022-07-04T11:15:33 Z Peti Road Construction (JOI21_road_construction) C++14
33 / 100
 2289 ms 26272 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 157 ms 7220 KB Output is correct
2 Correct 152 ms 6940 KB Output is correct
3 Correct 143 ms 6980 KB Output is correct
4 Correct 180 ms 6972 KB Output is correct
5 Incorrect 139 ms 5788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1538 ms 26140 KB Output is correct
2 Correct 1495 ms 26128 KB Output is correct
3 Correct 140 ms 6980 KB Output is correct
4 Correct 1255 ms 25948 KB Output is correct
5 Correct 1317 ms 26120 KB Output is correct
6 Correct 1266 ms 26272 KB Output is correct
7 Correct 935 ms 25512 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 17416 KB Output is correct
2 Correct 1840 ms 17456 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 587 ms 22684 KB Output is correct
5 Correct 541 ms 9596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 17416 KB Output is correct
2 Correct 1840 ms 17456 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 587 ms 22684 KB Output is correct
5 Correct 541 ms 9596 KB Output is correct
6 Correct 1545 ms 14448 KB Output is correct
7 Correct 1487 ms 14392 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2289 ms 17676 KB Output is correct
11 Correct 713 ms 22732 KB Output is correct
12 Correct 593 ms 9608 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 7220 KB Output is correct
2 Correct 152 ms 6940 KB Output is correct
3 Correct 143 ms 6980 KB Output is correct
4 Correct 180 ms 6972 KB Output is correct
5 Incorrect 139 ms 5788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 7220 KB Output is correct
2 Correct 152 ms 6940 KB Output is correct
3 Correct 143 ms 6980 KB Output is correct
4 Correct 180 ms 6972 KB Output is correct
5 Incorrect 139 ms 5788 KB Output isn't correct
6 Halted 0 ms 0 KB -