# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
389012 | georgerapeanu | Road Construction (JOI21_road_construction) | C++11 | 10024 ms | 24204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |