oj.uz

Submission #521651

# Submission time Handle Problem Language Result Execution time Memory
521651 2022-02-02T16:46:33 Z new_acc Road Construction (JOI21_road_construction) C++14
100 / 100
 9221 ms 603616 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((ll)w[j].fi-(ll)nn.fi),abs((ll)w[j].se-(ll)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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 208136 KB Output is correct
2 Correct 214 ms 208104 KB Output is correct
3 Correct 188 ms 207036 KB Output is correct
4 Correct 189 ms 207072 KB Output is correct
5 Correct 198 ms 207204 KB Output is correct
6 Correct 130 ms 202948 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2332 ms 570232 KB Output is correct
2 Correct 2253 ms 570188 KB Output is correct
3 Correct 197 ms 206928 KB Output is correct
4 Correct 2159 ms 581904 KB Output is correct
5 Correct 2239 ms 567424 KB Output is correct
6 Correct 2272 ms 568188 KB Output is correct
7 Correct 2314 ms 569528 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5570 ms 594456 KB Output is correct
2 Correct 5751 ms 594564 KB Output is correct
3 Correct 129 ms 202180 KB Output is correct
4 Correct 2111 ms 566352 KB Output is correct
5 Correct 5285 ms 486352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5570 ms 594456 KB Output is correct
2 Correct 5751 ms 594564 KB Output is correct
3 Correct 129 ms 202180 KB Output is correct
4 Correct 2111 ms 566352 KB Output is correct
5 Correct 5285 ms 486352 KB Output is correct
6 Correct 5834 ms 582548 KB Output is correct
7 Correct 5826 ms 594404 KB Output is correct
8 Correct 128 ms 202236 KB Output is correct
9 Correct 127 ms 202308 KB Output is correct
10 Correct 5674 ms 597092 KB Output is correct
11 Correct 2135 ms 567840 KB Output is correct
12 Correct 5006 ms 491656 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 208136 KB Output is correct
2 Correct 214 ms 208104 KB Output is correct
3 Correct 188 ms 207036 KB Output is correct
4 Correct 189 ms 207072 KB Output is correct
5 Correct 198 ms 207204 KB Output is correct
6 Correct 130 ms 202948 KB Output is correct
7 Correct 3545 ms 365436 KB Output is correct
8 Correct 3505 ms 365316 KB Output is correct
9 Correct 198 ms 207152 KB Output is correct
10 Correct 2633 ms 362888 KB Output is correct
11 Correct 2040 ms 361232 KB Output is correct
12 Correct 1613 ms 277252 KB Output is correct
13 Correct 2626 ms 286288 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 208136 KB Output is correct
2 Correct 214 ms 208104 KB Output is correct
3 Correct 188 ms 207036 KB Output is correct
4 Correct 189 ms 207072 KB Output is correct
5 Correct 198 ms 207204 KB Output is correct
6 Correct 130 ms 202948 KB Output is correct
7 Correct 2332 ms 570232 KB Output is correct
8 Correct 2253 ms 570188 KB Output is correct
9 Correct 197 ms 206928 KB Output is correct
10 Correct 2159 ms 581904 KB Output is correct
11 Correct 2239 ms 567424 KB Output is correct
12 Correct 2272 ms 568188 KB Output is correct
13 Correct 2314 ms 569528 KB Output is correct
14 Correct 5570 ms 594456 KB Output is correct
15 Correct 5751 ms 594564 KB Output is correct
16 Correct 129 ms 202180 KB Output is correct
17 Correct 2111 ms 566352 KB Output is correct
18 Correct 5285 ms 486352 KB Output is correct
19 Correct 5834 ms 582548 KB Output is correct
20 Correct 5826 ms 594404 KB Output is correct
21 Correct 128 ms 202236 KB Output is correct
22 Correct 127 ms 202308 KB Output is correct
23 Correct 5674 ms 597092 KB Output is correct
24 Correct 2135 ms 567840 KB Output is correct
25 Correct 5006 ms 491656 KB Output is correct
26 Correct 3545 ms 365436 KB Output is correct
27 Correct 3505 ms 365316 KB Output is correct
28 Correct 198 ms 207152 KB Output is correct
29 Correct 2633 ms 362888 KB Output is correct
30 Correct 2040 ms 361232 KB Output is correct
31 Correct 1613 ms 277252 KB Output is correct
32 Correct 2626 ms 286288 KB Output is correct
33 Correct 9221 ms 603544 KB Output is correct
34 Correct 9205 ms 603616 KB Output is correct
35 Correct 6928 ms 594920 KB Output is correct
36 Correct 4419 ms 328644 KB Output is correct
37 Correct 4742 ms 305076 KB Output is correct
38 Correct 6309 ms 400208 KB Output is correct