oj.uz

Submission #389013

# Submission time Handle Problem Language Result Execution time Memory
389013 2021-04-13T13:16:20 Z georgerapeanu Road Construction (JOI21_road_construction) C++11
38 / 100
 10000 ms 24148 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 25e4;

int n,k;

map<long long,int> to_norm;
pair<long long,long long> 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(long long 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<long long> get_distances(long long dist){
    vector<long long> 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;
    }

    long long l = 0;
    long long r = 4e9 + 5;

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

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

    vector<long long> ans = get_distances(l);

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

    for(auto it:ans){
        printf("%lld\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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5020 KB Output is correct
2 Correct 69 ms 5044 KB Output is correct
3 Correct 60 ms 5008 KB Output is correct
4 Correct 59 ms 5084 KB Output is correct
5 Correct 60 ms 3912 KB Output is correct
6 Correct 5 ms 332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5537 ms 24080 KB Output is correct
2 Correct 5484 ms 24020 KB Output is correct
3 Correct 54 ms 4964 KB Output is correct
4 Correct 5638 ms 23904 KB Output is correct
5 Correct 5883 ms 24148 KB Output is correct
6 Correct 5914 ms 24144 KB Output is correct
7 Correct 5531 ms 23380 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10056 ms 20796 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 10056 ms 20796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5020 KB Output is correct
2 Correct 69 ms 5044 KB Output is correct
3 Correct 60 ms 5008 KB Output is correct
4 Correct 59 ms 5084 KB Output is correct
5 Correct 60 ms 3912 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 6273 ms 14624 KB Output is correct
8 Correct 6425 ms 14632 KB Output is correct
9 Correct 58 ms 5024 KB Output is correct
10 Correct 5264 ms 13032 KB Output is correct
11 Correct 4257 ms 12584 KB Output is correct
12 Correct 1198 ms 8372 KB Output is correct
13 Correct 1384 ms 7020 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5020 KB Output is correct
2 Correct 69 ms 5044 KB Output is correct
3 Correct 60 ms 5008 KB Output is correct
4 Correct 59 ms 5084 KB Output is correct
5 Correct 60 ms 3912 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 5537 ms 24080 KB Output is correct
8 Correct 5484 ms 24020 KB Output is correct
9 Correct 54 ms 4964 KB Output is correct
10 Correct 5638 ms 23904 KB Output is correct
11 Correct 5883 ms 24148 KB Output is correct
12 Correct 5914 ms 24144 KB Output is correct
13 Correct 5531 ms 23380 KB Output is correct
14 Execution timed out 10056 ms 20796 KB Time limit exceeded
15 Halted 0 ms 0 KB -