oj.uz

Submission #684353

# Submission time Handle Problem Language Result Execution time Memory
684353 2023-01-21T03:04:01 Z arnold518 Road Construction (JOI21_road_construction) C++17
100 / 100
 8722 ms 85040 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 29556 KB Output is correct
2 Correct 70 ms 29560 KB Output is correct
3 Correct 73 ms 29556 KB Output is correct
4 Correct 62 ms 29668 KB Output is correct
5 Correct 65 ms 28476 KB Output is correct
6 Correct 25 ms 24964 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4082 ms 79664 KB Output is correct
2 Correct 4008 ms 79500 KB Output is correct
3 Correct 58 ms 29496 KB Output is correct
4 Correct 3963 ms 79356 KB Output is correct
5 Correct 3801 ms 79600 KB Output is correct
6 Correct 3879 ms 79632 KB Output is correct
7 Correct 3835 ms 78888 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7728 ms 78524 KB Output is correct
2 Correct 7809 ms 78464 KB Output is correct
3 Correct 14 ms 24660 KB Output is correct
4 Correct 3800 ms 76216 KB Output is correct
5 Correct 4723 ms 69536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7728 ms 78524 KB Output is correct
2 Correct 7809 ms 78464 KB Output is correct
3 Correct 14 ms 24660 KB Output is correct
4 Correct 3800 ms 76216 KB Output is correct
5 Correct 4723 ms 69536 KB Output is correct
6 Correct 8082 ms 78276 KB Output is correct
7 Correct 7891 ms 78404 KB Output is correct
8 Correct 14 ms 24652 KB Output is correct
9 Correct 13 ms 24660 KB Output is correct
10 Correct 7817 ms 82976 KB Output is correct
11 Correct 3769 ms 76376 KB Output is correct
12 Correct 4754 ms 69188 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 29556 KB Output is correct
2 Correct 70 ms 29560 KB Output is correct
3 Correct 73 ms 29556 KB Output is correct
4 Correct 62 ms 29668 KB Output is correct
5 Correct 65 ms 28476 KB Output is correct
6 Correct 25 ms 24964 KB Output is correct
7 Correct 3268 ms 51020 KB Output is correct
8 Correct 3159 ms 51060 KB Output is correct
9 Correct 63 ms 29624 KB Output is correct
10 Correct 2929 ms 49036 KB Output is correct
11 Correct 2700 ms 48952 KB Output is correct
12 Correct 1738 ms 45056 KB Output is correct
13 Correct 1740 ms 45428 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 29556 KB Output is correct
2 Correct 70 ms 29560 KB Output is correct
3 Correct 73 ms 29556 KB Output is correct
4 Correct 62 ms 29668 KB Output is correct
5 Correct 65 ms 28476 KB Output is correct
6 Correct 25 ms 24964 KB Output is correct
7 Correct 4082 ms 79664 KB Output is correct
8 Correct 4008 ms 79500 KB Output is correct
9 Correct 58 ms 29496 KB Output is correct
10 Correct 3963 ms 79356 KB Output is correct
11 Correct 3801 ms 79600 KB Output is correct
12 Correct 3879 ms 79632 KB Output is correct
13 Correct 3835 ms 78888 KB Output is correct
14 Correct 7728 ms 78524 KB Output is correct
15 Correct 7809 ms 78464 KB Output is correct
16 Correct 14 ms 24660 KB Output is correct
17 Correct 3800 ms 76216 KB Output is correct
18 Correct 4723 ms 69536 KB Output is correct
19 Correct 8082 ms 78276 KB Output is correct
20 Correct 7891 ms 78404 KB Output is correct
21 Correct 14 ms 24652 KB Output is correct
22 Correct 13 ms 24660 KB Output is correct
23 Correct 7817 ms 82976 KB Output is correct
24 Correct 3769 ms 76376 KB Output is correct
25 Correct 4754 ms 69188 KB Output is correct
26 Correct 3268 ms 51020 KB Output is correct
27 Correct 3159 ms 51060 KB Output is correct
28 Correct 63 ms 29624 KB Output is correct
29 Correct 2929 ms 49036 KB Output is correct
30 Correct 2700 ms 48952 KB Output is correct
31 Correct 1738 ms 45056 KB Output is correct
32 Correct 1740 ms 45428 KB Output is correct
33 Correct 8722 ms 82452 KB Output is correct
34 Correct 8525 ms 82564 KB Output is correct
35 Correct 7820 ms 85040 KB Output is correct
36 Correct 4263 ms 69144 KB Output is correct
37 Correct 4312 ms 69236 KB Output is correct
38 Correct 4909 ms 72644 KB Output is correct