oj.uz

답안 #521371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521371 2022-02-02T01:41:57 Z new_acc Road Construction (JOI21_road_construction) C++14
5 / 100
 10000 ms 2097156 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(size_t a = 0; a < (b); a++)
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=3e5+10;
const ll SS=1LL<<31;
struct item{
	deque<int>deq;
	int val;
	item *l,*r;
};
vi wyn;
vector<pair<ll,ll> >w;
bool bb[N];
vector<ll> ans;
void Insert(pitem v,ll ind,int x,int xd,ll l=SS*(-1),ll r=SS-1){
	v->val+=x;
	if(l==r) {
		if(x==-1) v->deq.pop_front();
		else v->deq.push_back(xd);
		return;
	}
	ll sr=l+(r-l)/2LL;
	if(ind>sr){
		if(!(v->r)){
			pitem xd=new item;
			xd->l=nullptr,xd->r=nullptr,xd->val=0;
			v->r=xd;
		}
		Insert(v->r,ind,x,xd,sr+1,r);
	}else{
		if(!(v->l)){
			pitem xd=new item;
			xd->l=nullptr,xd->r=nullptr,xd->val=0;
			v->l=xd;
		}
		Insert(v->l,ind,x,xd,l,sr);
	}
}
void clear(pitem v){
	if(!v) return;
	clear(v->l),clear(v->r);
	delete v;
}
int Query(pitem v,ll pocz,ll kon,ll p=SS*(-1),ll k=SS-1){
	if(p>kon or k<pocz or !v) return 0;
	if(p>=pocz and k<=kon) return v->val;
	else{
		ll sr=p+(k-p)/2;
		return Query(v->l,pocz,kon,p,sr)+Query(v->r,pocz,kon,sr+1,k);
	}
}
void divide(ll l,ll r,pitem v,int k){
	if(!v or (int)wyn.size()==k) return;
	if(v->val==0) return;
	if(l==r){
		deque<int>dd=v->deq;
		while(dd.size() and wyn.size()<k){
			wyn.push_back(dd.front());
			dd.pop_front();
		}
		return;
	}
	ll sr=l+(r-l)/2;
	divide(l,sr,v->l,k),divide(sr+1,r,v->r,k);
}
void Query2(pitem v,ll pocz,ll kon,int kk,ll p=SS*(-1),ll k=SS-1){
	if(p>kon or k<pocz or !v) return;
	if(p>=pocz and k<=kon) divide(p,k,v,kk);
	else{
		ll sr=p+(k-p)/2;
		Query2(v->l,pocz,kon,kk,p,sr),Query2(v->r,pocz,kon,kk,sr+1,k);
	}
}
bool check(ll x,ll l){;
	int wsk=0;
	pitem k=new item;
	k->val=0,k->l=nullptr,k->r=nullptr;
	ll res=0;
	rep(i,w.size()){
		if(i and w[i].fi==w[i-1].fi) continue;
		int curr=i;
		while(w[wsk].fi<w[i].fi-x) Insert(k,w[wsk].se,-1,0),wsk++;
		while(curr<(int)w.size() and w[curr].fi==w[i].fi) res+=(ll)Query(k,max(SS*(-1LL),(ll)w[curr].se-x),min(SS-1,(ll)w[curr].se+x)),Insert(k,w[curr].se,1,curr),curr++;
	}
	clear(k);
	return res>=l;
}
ll bs(ll l){
	ll pocz=1,kon=(ll)(1e9)*4;
	ll sr,res=0;
	while(pocz<=kon){
		sr=(pocz+kon)/2;
		if(check(sr,l)) res=sr,kon=sr-1;
		else pocz=sr+1;
	}
	return res;
}
void solve(){
	int n,il;
	cin>>n>>il;
	rep(i,n){
		int x,y;
		cin>>x>>y;
		int x1=x-y,y1=x+y;
		w.push_back({x1,y1});
	}
	sort(w.begin(),w.end());
	ll xd=bs(il);
	ll x,wsk;
	if(xd>1){
		x=xd-1;
		pitem k=new item;
		k->val=0,k->l=nullptr,k->r=nullptr;
		wsk=0;
		rep(i,w.size()){
			if(i and w[i].fi==w[i-1].fi) continue;
			int curr=i;
			while(w[wsk].fi<w[i].fi-x) Insert(k,w[wsk].se,-1,0),wsk++;
			while(curr<(int)w.size() and w[curr].fi==w[i].fi){
				Query2(k,max(SS*(-1LL),(ll)w[curr].se-x),min(SS-1,(ll)w[curr].se+x),il),Insert(k,w[curr].se,1,curr);
				rep(j,wyn.size()) ans.push_back(max(abs(w[curr].fi-w[wyn[j]].fi),abs(w[curr].se-w[wyn[j]].se)));
				curr++;
				wyn.clear();
			}
		}
		clear(k);
	}
	sort(ans.begin(),ans.end());
	rep(i,ans.size()) cout<<ans[i]<<"\n";
	for(int i=ans.size();i<il;i++) cout<<xd<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message

road_construction.cpp: In function 'void divide(ll, ll, item*, int)':
road_construction.cpp:63:33: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |   while(dd.size() and wyn.size()<k){
      |                       ~~~~~~~~~~^~
road_construction.cpp: In function 'void solve()':
road_construction.cpp:4:39: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    4 | #define rep(a, b) for(size_t a = 0; a < (b); a++)
      |                                       ^
road_construction.cpp:107:2: note: in expansion of macro 'rep'
  107 |  rep(i,n){
      |  ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 516 ms 20808 KB Output is correct
2 Correct 549 ms 20860 KB Output is correct
3 Correct 304 ms 16568 KB Output is correct
4 Correct 313 ms 16612 KB Output is correct
5 Correct 211 ms 12464 KB Output is correct
6 Correct 22 ms 972 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1302 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1380 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1380 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 516 ms 20808 KB Output is correct
2 Correct 549 ms 20860 KB Output is correct
3 Correct 304 ms 16568 KB Output is correct
4 Correct 313 ms 16612 KB Output is correct
5 Correct 211 ms 12464 KB Output is correct
6 Correct 22 ms 972 KB Output is correct
7 Execution timed out 10141 ms 1139352 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 516 ms 20808 KB Output is correct
2 Correct 549 ms 20860 KB Output is correct
3 Correct 304 ms 16568 KB Output is correct
4 Correct 313 ms 16612 KB Output is correct
5 Correct 211 ms 12464 KB Output is correct
6 Correct 22 ms 972 KB Output is correct
7 Runtime error 1302 ms 2097156 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -