Submission #618751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
618751	2022-08-02T07:13:13 Z	errorgorn	Road Construction (JOI21_road_construction)	C++17	100 / 100	6627 ms	66900 KB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int fen[250005];

void update(int i,int k){
	while (i<250005){
		fen[i]+=k;
		i+=i&-i;
	}
}

int query(int i){
	int res=0;
	while (i){
		res+=fen[i];
		i-=i&-i;
	}
	return res;
}

int query(int i,int j){
	return query(j)-query(i-1);
}

vector<int> vq;
struct node{
	int s,e,m;
	set<int> idx;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void add(int i,int k){
		idx.insert(k);
		
		if (s==e) return;
		else if (i<=m) l->add(i,k);
		else r->add(i,k);
	}
	
	void rem(int i,int k){
		idx.erase(k);
		
		if (s==e) return;
		else if (i<=m) l->rem(i,k);
		else r->rem(i,k);
	}
	
	void query(int i,int j){
		if (s==i && e==j){
			for (auto it:idx) vq.pub(it);
		}
		else if (j<=m) l->query(i,j);
		else if (m<i) r->query(i,j);
		else l->query(i,m),r->query(m+1,j);
	}
} *root=new node(0,250005);

int n,k;
ii arr[250005];

vector<int> uni={-(int)1e18}; //unique points in the y-direction

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	rep(x,1,n+1) arr[x]={arr[x].fi-arr[x].se,arr[x].fi+arr[x].se};
	sort(arr+1,arr+n+1);
	
	rep(x,1,n+1) uni.pub(arr[x].se);
	sort(all(uni));
	uni.erase(unique(all(uni)),uni.end());
	
	int lo=0,hi=4e9+100,mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		memset(fen,0,sizeof(fen));
		int l=1,r=0; //[l,r]
		int num=0;
		rep(x,1,n+1){
			while (r+1<=n && arr[r+1].fi<=arr[x].fi+mi){
				r++;
				int pos=lb(all(uni),arr[r].se)-uni.begin();
				update(pos,1);
			}
			while (l<=n && arr[l].fi<arr[x].fi-mi){
				int pos=lb(all(uni),arr[l].se)-uni.begin();
				update(pos,-1);
				l++;
			}
			
			int l=lb(all(uni),arr[x].se-mi)-uni.begin();
			int r=ub(all(uni),arr[x].se+mi)-uni.begin()-1;
			num+=query(l,r);
		}
		num=(num-n)/2;
		
		if (num>=k) hi=mi;
		else lo=mi;
	}
	
	vector<int> ans;
	int l=1,r=0;
	rep(x,1,n+1){
		while (r+1<=n && arr[r+1].fi<=arr[x].fi+lo){
			r++;
			int pos=lb(all(uni),arr[r].se)-uni.begin();
			root->add(pos,r);
		}
		while (l<=n && arr[l].fi<arr[x].fi-lo){
			int pos=lb(all(uni),arr[l].se)-uni.begin();
			root->rem(pos,l);
			l++;
		}
		
		int l=lb(all(uni),arr[x].se-lo)-uni.begin();
		int r=ub(all(uni),arr[x].se+lo)-uni.begin()-1;
		
		vq.clear();
		root->query(l,r);
		
		for (auto it:vq) if (it<x){
			ans.pub(max(abs(arr[x].fi-arr[it].fi),abs(arr[x].se-arr[it].se)));
		}
	}
	
	while (sz(ans)<k) ans.pub(hi);
	sort(all(ans));
	
	for (auto it:ans) cout<<it<<endl;
}

Compilation message

road_construction.cpp: In constructor 'node::node(long long int, long long int)':
road_construction.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:107:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |   mi=hi+lo>>1;
      |      ~~^~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	54532 KB	Output is correct
2	Correct	87 ms	54624 KB	Output is correct
3	Correct	81 ms	54580 KB	Output is correct
4	Correct	84 ms	54704 KB	Output is correct
5	Correct	91 ms	53472 KB	Output is correct
6	Correct	38 ms	49356 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2450 ms	58488 KB	Output is correct
2	Correct	2251 ms	58592 KB	Output is correct
3	Correct	83 ms	54496 KB	Output is correct
4	Correct	2188 ms	59088 KB	Output is correct
5	Correct	2179 ms	58672 KB	Output is correct
6	Correct	2161 ms	58700 KB	Output is correct
7	Correct	2246 ms	58464 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5264 ms	55452 KB	Output is correct
2	Correct	5256 ms	55444 KB	Output is correct
3	Correct	37 ms	49208 KB	Output is correct
4	Correct	2097 ms	55420 KB	Output is correct
5	Correct	2281 ms	56252 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5264 ms	55452 KB	Output is correct
2	Correct	5256 ms	55444 KB	Output is correct
3	Correct	37 ms	49208 KB	Output is correct
4	Correct	2097 ms	55420 KB	Output is correct
5	Correct	2281 ms	56252 KB	Output is correct
6	Correct	5311 ms	55476 KB	Output is correct
7	Correct	5396 ms	60232 KB	Output is correct
8	Correct	34 ms	49228 KB	Output is correct
9	Correct	32 ms	49216 KB	Output is correct
10	Correct	5275 ms	60300 KB	Output is correct
11	Correct	2116 ms	58172 KB	Output is correct
12	Correct	2573 ms	61240 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	54532 KB	Output is correct
2	Correct	87 ms	54624 KB	Output is correct
3	Correct	81 ms	54580 KB	Output is correct
4	Correct	84 ms	54704 KB	Output is correct
5	Correct	91 ms	53472 KB	Output is correct
6	Correct	38 ms	49356 KB	Output is correct
7	Correct	2619 ms	57028 KB	Output is correct
8	Correct	2570 ms	58784 KB	Output is correct
9	Correct	94 ms	54680 KB	Output is correct
10	Correct	2094 ms	57612 KB	Output is correct
11	Correct	1814 ms	57988 KB	Output is correct
12	Correct	802 ms	59000 KB	Output is correct
13	Correct	948 ms	57592 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	54532 KB	Output is correct
2	Correct	87 ms	54624 KB	Output is correct
3	Correct	81 ms	54580 KB	Output is correct
4	Correct	84 ms	54704 KB	Output is correct
5	Correct	91 ms	53472 KB	Output is correct
6	Correct	38 ms	49356 KB	Output is correct
7	Correct	2450 ms	58488 KB	Output is correct
8	Correct	2251 ms	58592 KB	Output is correct
9	Correct	83 ms	54496 KB	Output is correct
10	Correct	2188 ms	59088 KB	Output is correct
11	Correct	2179 ms	58672 KB	Output is correct
12	Correct	2161 ms	58700 KB	Output is correct
13	Correct	2246 ms	58464 KB	Output is correct
14	Correct	5264 ms	55452 KB	Output is correct
15	Correct	5256 ms	55444 KB	Output is correct
16	Correct	37 ms	49208 KB	Output is correct
17	Correct	2097 ms	55420 KB	Output is correct
18	Correct	2281 ms	56252 KB	Output is correct
19	Correct	5311 ms	55476 KB	Output is correct
20	Correct	5396 ms	60232 KB	Output is correct
21	Correct	34 ms	49228 KB	Output is correct
22	Correct	32 ms	49216 KB	Output is correct
23	Correct	5275 ms	60300 KB	Output is correct
24	Correct	2116 ms	58172 KB	Output is correct
25	Correct	2573 ms	61240 KB	Output is correct
26	Correct	2619 ms	57028 KB	Output is correct
27	Correct	2570 ms	58784 KB	Output is correct
28	Correct	94 ms	54680 KB	Output is correct
29	Correct	2094 ms	57612 KB	Output is correct
30	Correct	1814 ms	57988 KB	Output is correct
31	Correct	802 ms	59000 KB	Output is correct
32	Correct	948 ms	57592 KB	Output is correct
33	Correct	6524 ms	66412 KB	Output is correct
34	Correct	6627 ms	66432 KB	Output is correct
35	Correct	5360 ms	64128 KB	Output is correct
36	Correct	1958 ms	66900 KB	Output is correct
37	Correct	1973 ms	66872 KB	Output is correct
38	Correct	2359 ms	65480 KB	Output is correct