oj.uz

답안 #521650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521650 2022-02-02T16:42:30 Z new_acc Road Construction (JOI21_road_construction) C++14
13 / 100
 5869 ms 599712 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;
struct item{
	int val,sum,il;
	ll prior;
	item *l,*r;
};
vector<pair<int,int> >w;
bool bb[N];
vector<ll> ans;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
unordered_map<int,int>m;
deque<int> deq[N];
pair<pitem,pitem> split(pitem v,int x){
	if(!v) return {nullptr,nullptr};
	if((v->val)<=x){
		pair<pitem,pitem> p=split(v->r,x);
		v->r=p.fi;
		v->sum=((v->l)!=nullptr?v->l->sum:0)+((v->r)!=nullptr?v->r->sum:0)+(v->il);
		return {v,p.se};
	}else{
		pair<pitem,pitem> p=split(v->l,x);
		v->l=p.se;
		v->sum=((v->l)!=nullptr?v->l->sum:0)+((v->r)!=nullptr?v->r->sum:0)+(v->il);
		return {p.fi,v};
	}
}
pitem merge(pitem v1,pitem v2){
	if(!v1 or !v2) return (!v1?v2:v1);
	if((v1->prior)>(v2->prior)){
		v1->r=merge(v1->r,v2);
		v1->sum=((v1->l)!=nullptr?v1->l->sum:0)+((v1->r)!=nullptr?v1->r->sum:0)+(v1->il);
		return v1;
	}else{
		v2->l=merge(v1,v2->l);
		v2->sum=((v2->l)!=nullptr?v2->l->sum:0)+((v2->r)!=nullptr?v2->r->sum:0)+(v2->il);
		return v2;
	}
}
pitem add(pitem v,int a){
	pair<pitem,pitem> curr=split(v,a);
	pair<pitem,pitem> curr2=split(curr.fi,a-1);
	if(!curr2.se){
		pitem nn=new item;
		nn->val=a,nn->il=1,nn->sum=1,nn->l=nullptr,nn->r=nullptr;
		nn->prior=uniform_int_distribution<ll>(1,1000LL*1000LL*1000LL*1000LL)(rng);
		v=merge(merge(curr2.fi,nn),curr.se);
	}else{
		curr2.se->il++,curr2.se->sum++;
		v=merge(merge(curr2.fi,curr2.se),curr.se);
	}
	return v;
}	
pitem del(pitem v,int a){
	pair<pitem,pitem> curr=split(v,a);
	pair<pitem,pitem> curr2=split(curr.fi,a-1);
	if(curr2.se->il==1) v=merge(curr2.fi,curr.se);
	else{
		curr2.se->il--,curr2.se->sum--;
		v=merge(merge(curr2.fi,curr2.se),curr.se);
	}
	return v;
}
void clear(pitem v){
	if(!v) return;
	clear(v->l),clear(v->r);
	delete v;
}
bool check(ll x,ll l){;
	int wsk=0;
	pitem k=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) k=del(k,w[wsk].se),wsk++;
		while(curr<(int)w.size() and w[curr].fi==w[i].fi){
			pair<int,int>prz={max((ll)1e9*2LL*(-1),w[curr].se-x),min((ll)1e9*2LL,w[curr].se+x)};
			pair<pitem,pitem> c=split(k,prz.se);
			pair<pitem,pitem> curr2=split(c.fi,prz.fi-1);
			res+=(!curr2.se?0:curr2.se->sum);
			k=merge(merge(curr2.fi,curr2.se),c.se);
			k=add(k,w[curr].se);
			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 odczyt(pitem k,int j){
	if(!k) return;
	deque<int> d=deq[m[k->val]];
	while(d.size()){
		pair<int,int> nn={d.front(),k->val};
		ans.push_back(max(abs(w[j].fi-nn.fi),abs(w[j].se-nn.se)));
		d.pop_front();
	}
	odczyt(k->l,j),odczyt(k->r,j);
}
void solve(){
	pitem k=nullptr;
	k=add(k,2);
	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(),[](pair<int,int> a,pair<int,int> b){
		return a.se<b.se;
	});
	int akt=0;
	rep(i,w.size()) if(!i or w[i].se!=w[i-1].se) m[w[i].se]=akt++;
	sort(w.begin(),w.end());
	ll xd=bs(il);
	if(xd!=1){
		ll x=xd-1,wsk=0;	
		pitem k=nullptr;
		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) deq[m[w[wsk].se]].pop_front(),k=del(k,w[wsk].se),wsk++;
			while(curr<(int)w.size() and w[curr].fi==w[i].fi){
				pair<int,int>prz={max((ll)1e9*2LL*(-1),w[curr].se-x),min((ll)1e9*2LL,w[curr].se+x)};
				pair<pitem,pitem> c=split(k,prz.se);
				pair<pitem,pitem> curr2=split(c.fi,prz.fi-1);
				odczyt(curr2.se,curr);
				k=merge(merge(curr2.fi,curr2.se),c.se);
				k=add(k,w[curr].se);
				deq[m[w[curr].se]].push_back(w[curr].fi);
				curr++;
			}
		}	
	}
	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 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:123:2: note: in expansion of macro 'rep'
  123 |  rep(i,n){
      |  ^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 208152 KB Output is correct
2 Correct 216 ms 208196 KB Output is correct
3 Incorrect 198 ms 207132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2311 ms 573280 KB Output is correct
2 Correct 2258 ms 573276 KB Output is correct
3 Correct 193 ms 206932 KB Output is correct
4 Correct 2163 ms 584804 KB Output is correct
5 Correct 2268 ms 570436 KB Output is correct
6 Correct 2256 ms 571228 KB Output is correct
7 Correct 2312 ms 572624 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5586 ms 599672 KB Output is correct
2 Correct 5648 ms 599712 KB Output is correct
3 Correct 128 ms 202260 KB Output is correct
4 Correct 2075 ms 569276 KB Output is correct
5 Correct 5294 ms 491872 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5586 ms 599672 KB Output is correct
2 Correct 5648 ms 599712 KB Output is correct
3 Correct 128 ms 202260 KB Output is correct
4 Correct 2075 ms 569276 KB Output is correct
5 Correct 5294 ms 491872 KB Output is correct
6 Correct 5805 ms 587744 KB Output is correct
7 Correct 5869 ms 599456 KB Output is correct
8 Correct 127 ms 202180 KB Output is correct
9 Incorrect 134 ms 202220 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 208152 KB Output is correct
2 Correct 216 ms 208196 KB Output is correct
3 Incorrect 198 ms 207132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 208152 KB Output is correct
2 Correct 216 ms 208196 KB Output is correct
3 Incorrect 198 ms 207132 KB Output isn't correct
4 Halted 0 ms 0 KB -