oj.uz

Submission #389012

# Submission time Handle Problem Language Result Execution time Memory
389012 2021-04-13T13:12:19 Z georgerapeanu Road Construction (JOI21_road_construction) C++11
6 / 100
 10000 ms 24204 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 25e4;

int n,k;

map<long long,int> to_norm;
pair<int,int> v[NMAX + 5];

class FenwickTree{
    vector<int> aib;
    int n;

public:

    FenwickTree(int n){
        this->n = n;
        this->aib = vector<int>(n + 1);
    }

    void update(int pos,int value){
        for(;pos <= n;pos += (-pos) & pos){
            aib[pos] += value;
        }
    }

    int query(int pos){
        int ans = 0;
        for(;pos;pos -= (-pos) & pos){
            ans += aib[pos];
        }
        return ans;
    }
    
    void reset(){
        for(auto &it:aib){
            it = 0;
        }
    }

}aib(0);

long long get_count(int dist){
    aib.reset();
    int lst = 1;
    long long ans = 0;

    for(int i = 1;i <= n;i++){
        while(1LL * v[i].first - v[lst].first > dist){
            long long l = 1LL * v[lst].second - dist;
            long long r = 1LL * v[lst].second + dist;
            aib.update(to_norm.lower_bound(l)->second,-1);
            if(to_norm.lower_bound(r + 1) != to_norm.end()){
                aib.update(to_norm.lower_bound(r + 1)->second,1);
            }
            lst++;
        }

        ans += aib.query(to_norm[v[i].second]);
        long long l = 1LL * v[i].second - dist;
        long long r = 1LL * v[i].second + dist;

        aib.update(to_norm.lower_bound(l)->second,1);
        if(to_norm.lower_bound(r + 1) != to_norm.end()){
           aib.update(to_norm.lower_bound(r + 1)->second,-1);
        }
    }

    return ans;
}

vector<int> get_distances(int dist){
    vector<int> ans;
    int lst = 1;
    set<pair<long long,long long> > s;
    for(int i = 1;i <= n;i++){
        while(1LL * v[i].first - v[lst].first > dist){
            s.erase({v[lst].second,v[lst].first});
            lst++;
        }
        for(set<pair<long long,long long> > :: iterator it = s.lower_bound({1LL * v[i].second - dist,-2e9 - 10});it != s.end() && it->first <= 1LL * v[i].second + dist;it++){
            ans.push_back(max(abs(v[i].first - it->second),abs(v[i].second - it->first)));
        }
        s.insert({v[i].second,v[i].first});
    }

    sort(ans.begin(),ans.end());
    return ans;
}

int main(){
    
    scanf("%d %d",&n,&k);

    aib = FenwickTree(n);

    for(int i = 1;i <= n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        v[i] = {x + y,x - y};
        to_norm[v[i].second] = 1;
    }

    sort(v + 1,v + 1 + n);

    int lst = 0;

    for(auto &it:to_norm){
        it.second = ++lst;
    }

    int l = 0;
    int r = 2e9;

    while(r - l > 1){
        int mid = (1LL * l + 1LL * r) / 2;

        if(get_count(mid) < k){
            l = mid;
        }else{
            r = mid;
        }
    }

    vector<int> ans = get_distances(l);

    while((int)ans.size() < k){
        ans.push_back(r);
    }

    for(auto it:ans){
        printf("%d\n",it);
    }
    
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
road_construction.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4172 KB Output is correct
2 Correct 70 ms 3984 KB Output is correct
3 Incorrect 56 ms 4012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5493 ms 24196 KB Output is correct
2 Correct 5370 ms 24204 KB Output is correct
3 Correct 52 ms 3892 KB Output is correct
4 Correct 5644 ms 23956 KB Output is correct
5 Correct 5721 ms 24116 KB Output is correct
6 Correct 5856 ms 24204 KB Output is correct
7 Correct 5349 ms 23528 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10024 ms 23956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10024 ms 23956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4172 KB Output is correct
2 Correct 70 ms 3984 KB Output is correct
3 Incorrect 56 ms 4012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4172 KB Output is correct
2 Correct 70 ms 3984 KB Output is correct
3 Incorrect 56 ms 4012 KB Output isn't correct
4 Halted 0 ms 0 KB -