oj.uz

Submission #386295

# Submission time Handle Problem Language Result Execution time Memory
386295 2021-04-06T09:54:45 Z kshitij_sodani Road Construction (JOI21_road_construction) C++14
100 / 100
 3097 ms 565084 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n,k;
llo aa[300001];
llo bb[300001];
pair<llo,llo> tree[30*600001];
llo ll[30*700001];
llo rr[30*700001];
pair<llo,llo> le[300001];
llo mm[3000001];
pair<llo,llo> re[300001];
llo nn[3000001];
vector<pair<llo,llo>> ss;
llo cur=0;
llo build(llo l,llo r){
	llo cot=cur;
	cur++;
	if(l==r){
		tree[cot]={(llo)1e18,l};
		return cot;
	}
	else{
		llo mid=(l+r)/2;
		ll[cot]=build(l,mid);
		rr[cot]=build(mid+1,r);
		
		if(tree[ll[cot]].a<=tree[rr[cot]].a){
			tree[cot]=tree[ll[cot]];
		}
		else{
			tree[cot]=tree[rr[cot]];
		}
		return cot;
	}
}
llo update(llo no,llo l,llo r,llo i,llo val){
	llo cot=cur;
	cur++;
	if(l==r){
		tree[cot]={val,l};
	}
	else{
		ll[cot]=ll[no];
		rr[cot]=rr[no];
		llo mid=(l+r)/2;
		if(i<=mid){
			ll[cot]=update(ll[cot],l,mid,i,val);
		}
		else{
			rr[cot]=update(rr[cot],mid+1,r,i,val);
		}
		if(tree[ll[cot]].a<=tree[rr[cot]].a){
			tree[cot]=tree[ll[cot]];
		}
		else{
			tree[cot]=tree[rr[cot]];
		}
	}
	return cot;
}
pair<llo,llo> query(llo no,llo l,llo r,llo aa,llo bb){
	if(aa>bb or r<aa or l>bb){
		return {1e18,-1}; 
	}
	else if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		pair<llo,llo> xx=query(ll[no],l,mid,aa,bb);
		pair<llo,llo> yy=query(rr[no],mid+1,r,aa,bb);
		if(xx.a<=yy.a){
			return xx;
		}
		else{
			return yy;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(llo i=0;i<n;i++){
		cin>>aa[i];
		cin>>bb[i];
		ss.pb({aa[i],-bb[i]});
	}
	sort(ss.begin(),ss.end());
	for(int i=0;i<ss.size();i++){
		ss[i].b=-ss[i].b;
	}
	/*vector<int> tt;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			tt.pb(abs(aa[i]-aa[j])+abs(bb[i]-bb[j]));
		}
	}
	sort(tt.begin(),tt.end());*/
	/*for(int i=0;i<n;i++){
		cout<<ss[i].a<<","<<ss[i].b<<endl;
	}*/
	/*for(int i=0;i<k;i++){
		cout<<tt[i]<<" ";
	}
	cout<<endl;*/
	map<llo,llo> ind3;
	for(llo i=0;i<n;i++){
		ind3[ss[i].a]=i;
	}
	llo r1=build(0,n-1);//-x+y
	llo r2=build(0,n-1);//x+y;
	vector<pair<pair<llo,llo>,llo>> yy;

	for(llo i=0;i<n;i++){
		yy.pb({{-ss[i].b,ss[i].a},i});
	}
	sort(yy.begin(),yy.end());
	for(int j=0;j<yy.size();j++){
		yy[j].a.a=-yy[j].a.a;
	}
	vector<pair<pair<llo,llo>,llo>> root;
	root.pb({{r1,r2},((llo)1e18)});
	map<llo,llo> ind;
	map<llo,llo> ind2;
	llo co=0;
	for(auto j:yy){
		co++;
		r1=update(r1,0,n-1,j.b,-j.a.b+j.a.a);
	//	cout<<j.b<<"<<"<<-j.a.b+j.a.a<<endl;
		r2=update(r2,0,n-1,j.b,j.a.b+j.a.a);
		root.pb({{r1,r2},j.a.a});
		if(ind.find(j.a.a)==ind.end()){
			ind[j.a.a]=co;
		}
		ind2[j.a.a]=co;
	}
	/*for(auto j:root){
		cout<<j.a.a<<",,"<<j.a.b<<",,"<<j.b<<endl;
	}
	cout<<endl;*/
	//cout<<ind2[2]<<endl;
	priority_queue<pair<llo,llo>> xx;
	llo xy=0;
	/*for(auto j:yy){
		cout<<j.a.a<<","<<j.a.b<<":"<<j.b<<endl;
	}
	cout<<endl;*/
	for(auto j:yy){
		le[xy]=query(root[ind2[j.a.a]].a.a,0,n-1,0,j.b-1);
		
		le[xy].a+=j.a.b-j.a.a;;
		mm[xy]=root[ind2[j.a.a]].a.a;
		re[xy]=query(root[ind[j.a.a]-1].a.b,0,n-1,ind3[j.a.b]+1,n-1);
		re[xy].a-=(j.a.a+j.a.b);
		

		nn[xy]=root[ind[j.a.a]-1].a.b;
		//cout<<j.a.a<<","<<j.a.b<<":"<<j.b<<endl;
		//cout<<ind2[j.a.a]<<"::"<<0<<"::"<<j.b-1<<endl;
	//	cout<<le[xy].a<<":"<<re[xy].a<<endl;
	//	cout<<le[xy].b<<"<<"<<endl;
		//cout<<endl;
		xx.push({-min(re[xy].a,le[xy].a),xy});
		
		xy++;

	}
	for(int i=0;i<k;i++){
		pair<llo,llo> no=xx.top();
		xx.pop();
		cout<<(-no.a)<<endl;
		xy=no.b;
		pair<pair<llo,llo>,llo> j=yy[no.b];

		if(le[no.b].a<=re[no.b].a){
			/*if(le[no.b].b==-1){
				while(true){
					continue;
				}
			}*/
			//cout<<11<<endl;
			mm[xy]=update(mm[xy],0,n-1,le[xy].b,(llo)1e18);
		
			le[xy]=query(mm[xy],0,n-1,0,j.b-1);
			le[xy].a+=j.a.b-j.a.a;;
			//cout<<le[xy].a<<"<<"<<endl;
		}
		else{
			/*if(re[no.b].b==-1){
				while(true){
					continue;
				}
			}*/
			//cout<<11<<endl;
			nn[xy]=update(nn[xy],0,n-1,re[xy].b,(llo)1e18);
			re[xy]=query(nn[xy],0,n-1,ind3[j.a.b]+1,n-1);
			re[xy].a-=(j.a.a+j.a.b);
		}
		//cout<<no.b<<":"<<re[no.b].a<<":"<<le[j.b].a<<endl;
		xx.push({-min(re[no.b].a,le[no.b].a),xy});
	}



 
	return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:99:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
road_construction.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int j=0;j<yy.size();j++){
      |              ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 90172 KB Output is correct
2 Correct 406 ms 90092 KB Output is correct
3 Correct 375 ms 86252 KB Output is correct
4 Correct 321 ms 86500 KB Output is correct
5 Correct 366 ms 89032 KB Output is correct
6 Correct 5 ms 2156 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 533000 KB Output is correct
2 Correct 1253 ms 533180 KB Output is correct
3 Correct 227 ms 86384 KB Output is correct
4 Correct 1010 ms 532876 KB Output is correct
5 Correct 951 ms 533064 KB Output is correct
6 Correct 954 ms 533156 KB Output is correct
7 Correct 1004 ms 532296 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1995 ms 414652 KB Output is correct
2 Correct 1976 ms 414816 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 668 ms 383560 KB Output is correct
5 Correct 923 ms 367780 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1995 ms 414652 KB Output is correct
2 Correct 1976 ms 414816 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 668 ms 383560 KB Output is correct
5 Correct 923 ms 367780 KB Output is correct
6 Correct 2107 ms 414752 KB Output is correct
7 Correct 2071 ms 414700 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2041 ms 409300 KB Output is correct
11 Correct 677 ms 383432 KB Output is correct
12 Correct 914 ms 367800 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 90172 KB Output is correct
2 Correct 406 ms 90092 KB Output is correct
3 Correct 375 ms 86252 KB Output is correct
4 Correct 321 ms 86500 KB Output is correct
5 Correct 366 ms 89032 KB Output is correct
6 Correct 5 ms 2156 KB Output is correct
7 Correct 1620 ms 299108 KB Output is correct
8 Correct 1643 ms 299112 KB Output is correct
9 Correct 322 ms 86252 KB Output is correct
10 Correct 1182 ms 294792 KB Output is correct
11 Correct 1323 ms 293136 KB Output is correct
12 Correct 716 ms 280492 KB Output is correct
13 Correct 688 ms 279036 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 90172 KB Output is correct
2 Correct 406 ms 90092 KB Output is correct
3 Correct 375 ms 86252 KB Output is correct
4 Correct 321 ms 86500 KB Output is correct
5 Correct 366 ms 89032 KB Output is correct
6 Correct 5 ms 2156 KB Output is correct
7 Correct 1278 ms 533000 KB Output is correct
8 Correct 1253 ms 533180 KB Output is correct
9 Correct 227 ms 86384 KB Output is correct
10 Correct 1010 ms 532876 KB Output is correct
11 Correct 951 ms 533064 KB Output is correct
12 Correct 954 ms 533156 KB Output is correct
13 Correct 1004 ms 532296 KB Output is correct
14 Correct 1995 ms 414652 KB Output is correct
15 Correct 1976 ms 414816 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 668 ms 383560 KB Output is correct
18 Correct 923 ms 367780 KB Output is correct
19 Correct 2107 ms 414752 KB Output is correct
20 Correct 2071 ms 414700 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2041 ms 409300 KB Output is correct
24 Correct 677 ms 383432 KB Output is correct
25 Correct 914 ms 367800 KB Output is correct
26 Correct 1620 ms 299108 KB Output is correct
27 Correct 1643 ms 299112 KB Output is correct
28 Correct 322 ms 86252 KB Output is correct
29 Correct 1182 ms 294792 KB Output is correct
30 Correct 1323 ms 293136 KB Output is correct
31 Correct 716 ms 280492 KB Output is correct
32 Correct 688 ms 279036 KB Output is correct
33 Correct 3080 ms 565024 KB Output is correct
34 Correct 3097 ms 565084 KB Output is correct
35 Correct 2437 ms 548296 KB Output is correct
36 Correct 1337 ms 518144 KB Output is correct
37 Correct 1376 ms 518516 KB Output is correct
38 Correct 1348 ms 516832 KB Output is correct