Submission #684353

#	Time	Username	Problem	Language	Result	Execution time	Memory
684353		arnold518	Road Construction (JOI21_road_construction)	C++17	100 / 100	8722 ms	85040 KiB

road_construction

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 25e4;

int N, K;
pll A[MAXN+10], B[MAXN+10];
vector<ll> comp;

struct BIT
{
	int tree[MAXN+10];
	void update(int i) { for(; i<=MAXN; i+=(i&-i)) tree[i]++; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
	void memset() { fill(tree, tree+MAXN+10, 0); }
}bit;

ll f(ll X)
{
	bit.memset();
	vector<pll> V;
	for(int i=1; i<=N; i++)
	{
		V.push_back({B[i].first, i});
		V.push_back({B[i].first-X-1, i+N});
		V.push_back({B[i].first+X, i+N+N});
	}
	sort(V.begin(), V.end());

	ll ans=0;
	for(int i=0; i<V.size(); i++)
	{
		if(V[i].second<=N)
		{
			bit.update(lower_bound(comp.begin(), comp.end(), B[V[i].second].second)-comp.begin()+1);
		}
		else if(V[i].second<=N+N)
		{
			int r=upper_bound(comp.begin(), comp.end(), B[V[i].second-N].second+X)-comp.begin();
			int l=lower_bound(comp.begin(), comp.end(), B[V[i].second-N].second-X)-comp.begin();
			ans-=bit.query(r)-bit.query(l);
		}
		else
		{
			int r=upper_bound(comp.begin(), comp.end(), B[V[i].second-N-N].second+X)-comp.begin();
			int l=lower_bound(comp.begin(), comp.end(), B[V[i].second-N-N].second-X)-comp.begin();
			ans+=bit.query(r)-bit.query(l);
		}
	}
	ans-=N; ans/=2;
	//printf("%lld : %lld\n", X, ans);
	return ans;
}

ll dist(int x, int y)
{
	return abs(A[x].first-A[y].first)+abs(A[x].second-A[y].second);
}

vector<ll> ans;
struct SEG
{
	vector<int> tree[MAXN*4+10];
	void update(int node, int tl, int tr, int p, int q)
	{
		tree[node].push_back(q);
		if(tl==tr) return;
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid, p, q);
		else update(node*2+1, mid+1, tr, p, q);
	}
	void query(int node, int tl, int tr, int l, int r, int p, ll q)
	{
		if(l<=tl && tr<=r)
		{
			for(int i=tree[node].size()-1; i>=0 && dist(tree[node][i], p)<q; i--)
			{
				if(tree[node][i]<p) ans.push_back(dist(tree[node][i], p));
			}
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		query(node*2, tl, mid, l, r, p, q);
		query(node*2+1, mid+1, tr, l, r, p, q);
	}
}seg;

int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].first, &A[i].second);

	sort(A+1, A+N+1, [&](const pll &p, const pll &q) { return p.first+p.second<q.first+q.second; });
	for(int i=1; i<=N; i++)
	{
		B[i].first=A[i].first+A[i].second;
		B[i].second=A[i].first-A[i].second;
		comp.push_back(B[i].second);
	}

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());

	ll lo=0, hi=2e10;
	while(lo+1<hi)
	{
		ll mid=lo+hi>>1;
		if(f(mid)>=K) hi=mid;
		else lo=mid;
	}

	{
		ll X=hi-1;
		vector<pll> V;
		for(int i=1; i<=N; i++)
		{
			V.push_back({B[i].first, i});
			V.push_back({B[i].first+X, i+N});
		}
		sort(V.begin(), V.end());

		ll ans=0;
		for(int i=0; i<V.size(); i++)
		{
			if(V[i].second<=N)
			{
				seg.update(1, 1, N, lower_bound(comp.begin(), comp.end(), B[V[i].second].second)-comp.begin()+1, V[i].second);
			}
			else
			{
				int r=upper_bound(comp.begin(), comp.end(), B[V[i].second-N].second+X)-comp.begin();
				int l=lower_bound(comp.begin(), comp.end(), B[V[i].second-N].second-X)-comp.begin();
				seg.query(1, 1, N, l+1, r, V[i].second-N, hi);
			}
		}
	}

	sort(ans.begin(), ans.end());
	while(ans.size()<K) ans.push_back(hi);
	for(auto it : ans) printf("%lld\n", it);
}

Compilation message (stderr)

road_construction.cpp: In function 'll f(ll)':
road_construction.cpp:35:16: 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]
   35 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~
road_construction.cpp: In member function 'void SEG::update(int, int, int, int, int)':
road_construction.cpp:72:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   int mid=tl+tr>>1;
      |           ~~^~~
road_construction.cpp: In member function 'void SEG::query(int, int, int, int, int, int, ll)':
road_construction.cpp:87:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mid=tl+tr>>1;
      |           ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:112:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |   ll mid=lo+hi>>1;
      |          ~~^~~
road_construction.cpp:128:17: 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]
  128 |   for(int i=0; i<V.size(); i++)
      |                ~^~~~~~~~~
road_construction.cpp:127:6: warning: unused variable 'ans' [-Wunused-variable]
  127 |   ll ans=0;
      |      ^~~
road_construction.cpp:144:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |  while(ans.size()<K) ans.push_back(hi);
      |        ~~~~~~~~~~^~
road_construction.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
road_construction.cpp:96:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].first, &A[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35