oj.uz

Submission #389025

# Submission time Handle Problem Language Result Execution time Memory
389025 2021-04-13T13:50:37 Z georgerapeanu Road Construction (JOI21_road_construction) C++11
38 / 100
 10000 ms 24160 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(v[i].first - v[lst].first > dist){
            long long l = v[lst].second - dist;
            long long r = 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 = v[i].second - dist;
        long long r = 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(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({v[i].second - dist,-2e9 - 10});it != s.end() && it->first <= 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;
}

const int LEN = 1 << 12;
char buff[LEN];
int ind;

int i32(){
    int sgn = 1;
    int ans = 0;

    while((buff[ind] < '0' || buff[ind] > '9') && buff[ind] != '-'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }

    if(buff[ind] == '-'){
        sgn = -1;
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    
    while(!(buff[ind] < '0' || buff[ind] > '9')){
        ans = ans * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }

    return ans * sgn;
}


int main(){
    
    n = i32();
    k = i32();

    aib = FenwickTree(n);

    for(int i = 1;i <= n;i++){
        int x,y;
        x = i32();
        y = i32();
        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 = (l + 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 i32()':
road_construction.cpp:104:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  104 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp:112:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  112 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp:120:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  120 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4996 KB Output is correct
2 Correct 69 ms 5056 KB Output is correct
3 Correct 61 ms 5040 KB Output is correct
4 Correct 58 ms 5032 KB Output is correct
5 Correct 72 ms 3920 KB Output is correct
6 Correct 4 ms 332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5420 ms 24024 KB Output is correct
2 Correct 5472 ms 24032 KB Output is correct
3 Correct 56 ms 4952 KB Output is correct
4 Correct 5647 ms 23892 KB Output is correct
5 Correct 5871 ms 24148 KB Output is correct
6 Correct 5828 ms 24160 KB Output is correct
7 Correct 5494 ms 23508 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4996 KB Output is correct
2 Correct 69 ms 5056 KB Output is correct
3 Correct 61 ms 5040 KB Output is correct
4 Correct 58 ms 5032 KB Output is correct
5 Correct 72 ms 3920 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 6890 ms 12868 KB Output is correct
8 Correct 6505 ms 12924 KB Output is correct
9 Correct 58 ms 5124 KB Output is correct
10 Correct 5316 ms 11336 KB Output is correct
11 Correct 4365 ms 10820 KB Output is correct
12 Correct 1175 ms 6684 KB Output is correct
13 Correct 1331 ms 5164 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4996 KB Output is correct
2 Correct 69 ms 5056 KB Output is correct
3 Correct 61 ms 5040 KB Output is correct
4 Correct 58 ms 5032 KB Output is correct
5 Correct 72 ms 3920 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 5420 ms 24024 KB Output is correct
8 Correct 5472 ms 24032 KB Output is correct
9 Correct 56 ms 4952 KB Output is correct
10 Correct 5647 ms 23892 KB Output is correct
11 Correct 5871 ms 24148 KB Output is correct
12 Correct 5828 ms 24160 KB Output is correct
13 Correct 5494 ms 23508 KB Output is correct
14 Execution timed out 10007 ms 20840 KB Time limit exceeded
15 Halted 0 ms 0 KB -