| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 945808 | salmon | Road Construction (JOI21_road_construction) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int N,K;
vector<pair<long long int,int>> v;
long long int X,Y;
long long int lst[250100];
const long long int inf = 1e18 / 2 * 2;
vector<int> wacter;
long long int plop[250100];
struct node{
long long int s, m, e;
int num;
node *l,*r;
set<int> v;
node(long long int S, long long int E){
s = S;
e = E;
m = (s + e + inf)/2 - inf / 2;
num = 0;
l = NULL;
r = NULL;
}
void update(long long int i, int k, int p){
if(s == e){
num += k;
if(p != -1){
if(k == 1) v.insert(p);
else v.erase(p);
}
return;
}
num += k;
if(l == NULL){
l = new node(s,m);
r = new node(m + 1, e);
}
if(i <= m){
l -> update(i,k,p);
}
else{
r -> update(i,k,p);
}
}
int query(long long int S, long long int E){
if(S <= s && e <= E){
return num;
}
int V = 0;
if(l == NULL) return V;
if(S <= m){
V += l -> query(S,E);
}
if(m < E){
V += r -> query(S,E);
}
return V;
}
void banana(int S, int E){
if(S <= s && e <= E && s != e){
if(l == NULL) return;
if(l -> num > 0) l -> banana(S,E);
if(r -> num > 0) r -> banana(S,E);
return;
}
if(s == e){
for(int i : v){
wacter.push_back(i);
}
return;
}
int V = 0;
if(l == NULL) return;
if(S <= m){
l -> banana(S,E);
}
if(m < E){
r -> banana(S,E);
}
}
}*root;
int main(){
scanf(" %d",&N);
scanf(" %d",&K);
for(int i = 0; i < N; i++){
scanf(" %lld",&X);
scanf(" %lld",&Y);
v.push_back({X - Y,i});
lst[i] = X + Y;
plop[i] = X - Y;
}
v.push_back({1e16,-1});
sort(v.begin(),v.end());
long long int s = 0;
long long int e = 5e9;
while(s != e){
long long int m = (s + e)/2;
root = new node(0,2e10);
int num = 0;
int it1 = 0;
int it2 = 0;
for(int i = 0; i < N; i++){
while(v[it1].first + m < v[i].first){
root -> update(lst[v[it1].second],-1,-1);
it1++;
}
while(v[i].first + m >= v[it2].first){
root -> update(lst[v[it2].second],1,-1);
it2++;
}
num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
}
if(num / 2 >= K){
e = m;
}
else{
s = m + 1;
}
}
//printf("%d",s);
map<long long int,int> mep;
int it1 = 0;
int it2 = 0;
root = new node(-2e10,2e10);
for(int i = 0; i < N; i++){
while(v[i].first + s >= v[it2].first){
root -> update(lst[v[it2].second],1,v[it2].second);
it2++;
}
while(v[it1].first + s < v[i].first){
root -> update(lst[v[it1].second],-1,v[it1].second);
it1++;
}
root -> banana(lst[v[i].second] - s, lst[v[i].second] + s);
for(int j : wacter){
mep[max(abs(lst[j] - lst[v[i].second]) , abs(plop[j] - plop[v[i].second]) ) ]++;
}
wacter.clear();
}
vector<long long int> print;
mep.erase(0);
for(pair<long long int, int> ii : mep){
pair<long long int, int> temp = ii;
for(; K > 0 && temp.second > 0; K--, temp.second -= 2){
print.push_back(temp.first);
}
}
for(long long int i : print){
printf("%lld\n",i);
}
}
/*
5 1
1 -1
2 0
-1 0
0 2
0 -2
*/