oj.uz

Submission #439730

# Submission time Handle Problem Language Result Execution time Memory
439730 2021-06-30T16:37:39 Z kig9981 Road Construction (JOI21_road_construction) C++17
100 / 100
 6082 ms 44660 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const int SZ=1<<18;
vector<int> P[250000];
vector<pair<int,int>> U[250000];
vector<long long> ans, x, y;
int tree[2*SZ], X[250000], Y[250000];
 
void update(int n, int v)
{
	for(;n<=250000;n+=n&-n) tree[n]+=v;
}
 
int get_cnt(int n)
{
	int ret=0;
	for(;n;n-=n&-n) ret+=tree[n];
	return ret;
}
 
long long solve(long long K)
{
	int j=0;
	long long ret=0;
	memset(tree,0,sizeof(tree));
	for(int i=0;i<x.size();i++) {
		for(;x[j]+K<x[i];j++) for(auto[u,k]: U[j]) update(u+1,-1);
		for(auto[u,k]: U[i]) {
			ret+=get_cnt(upper_bound(y.begin(),y.end(),y[u]+K)-y.begin())-get_cnt(lower_bound(y.begin(),y.end(),y[u]-K)-y.begin());
			update(u+1,1);
		}
	}
	return ret;
}
 
void add_tree(int n, int i)
{
	P[n].push_back(i);
	for(tree[n+=SZ]++;n>>=1;) tree[n]=tree[2*n]+tree[2*n+1];
}
 
void get_ans(int n1, int n2, int i, long long K, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(n2<n1 || n2<s || e<n1 || tree[bit]==0) return;
	if(s==e) {
		for(int j=0;j<P[m].size();j++) {
			while(j<P[m].size() && 1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i])>K) {
				swap(P[m][j],P[m].back());
				P[m].pop_back();
				tree[bit]--;
			}
			if(j<P[m].size()) ans.push_back(1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i]));
		}
		return;
	}
	get_ans(n1,n2,i,K,2*bit,s,m);
	get_ans(n1,n2,i,K,2*bit+1,m+1,e);
	tree[bit]=tree[2*bit]+tree[2*bit+1];
}
 
long long solve2(long long K)
{
	long long ret=0;
	memset(tree,0,sizeof(tree));
	for(int i=0;i<x.size();i++) {
		for(auto[u,k]: U[i]) {
			get_ans((lower_bound(y.begin(),y.end(),y[u]-K)-y.begin()),(upper_bound(y.begin(),y.end(),y[u]+K)-y.begin()-1),k,K);
			add_tree(u,k);
		}
	}
	return ret;
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, K;
	long long s=0, e=4000000000LL;
	cin>>N>>K;
	for(int i=0;i<N;i++) {
		cin>>X[i]>>Y[i];
		x.push_back(X[i]+Y[i]);
		y.push_back(X[i]-Y[i]);
	}
	sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
	sort(y.begin(),y.end()); y.resize(unique(y.begin(),y.end())-y.begin());
	for(int i=0;i<N;i++) U[lower_bound(x.begin(),x.end(),X[i]+Y[i])-x.begin()].emplace_back(lower_bound(y.begin(),y.end(),X[i]-Y[i])-y.begin(),i);
	while(s<=e) {
		long long m=(s+e)>>1;
		if(solve(m)<K) s=m+1;
		else e=m-1;
	}
	solve2(e);
	sort(ans.begin(),ans.end());
	while(ans.size()<K) ans.push_back(s);
	for(auto a: ans) cout<<a<<'\n';
	return 0;
}

Compilation message

road_construction.cpp: In function 'long long int solve(long long int)':
road_construction.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<x.size();i++) {
      |              ~^~~~~~~~~
road_construction.cpp: In function 'void get_ans(int, int, int, long long int, int, int, int)':
road_construction.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j=0;j<P[m].size();j++) {
      |               ~^~~~~~~~~~~~
road_construction.cpp:58:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    while(j<P[m].size() && 1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i])>K) {
      |          ~^~~~~~~~~~~~
road_construction.cpp:63:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    if(j<P[m].size()) ans.push_back(1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i]));
      |       ~^~~~~~~~~~~~
road_construction.cpp: In function 'long long int solve2(long long int)':
road_construction.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i=0;i<x.size();i++) {
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:110:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  while(ans.size()<K) ans.push_back(s);
      |        ~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 18736 KB Output is correct
2 Correct 87 ms 18756 KB Output is correct
3 Correct 78 ms 18864 KB Output is correct
4 Correct 70 ms 18892 KB Output is correct
5 Correct 70 ms 17716 KB Output is correct
6 Correct 17 ms 14180 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2737 ms 38820 KB Output is correct
2 Correct 2783 ms 38812 KB Output is correct
3 Correct 65 ms 18736 KB Output is correct
4 Correct 2800 ms 38692 KB Output is correct
5 Correct 2966 ms 38868 KB Output is correct
6 Correct 2868 ms 38820 KB Output is correct
7 Correct 2906 ms 38004 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5372 ms 35616 KB Output is correct
2 Correct 5370 ms 35628 KB Output is correct
3 Correct 11 ms 14028 KB Output is correct
4 Correct 2582 ms 35612 KB Output is correct
5 Correct 1747 ms 23060 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5372 ms 35616 KB Output is correct
2 Correct 5370 ms 35628 KB Output is correct
3 Correct 11 ms 14028 KB Output is correct
4 Correct 2582 ms 35612 KB Output is correct
5 Correct 1747 ms 23060 KB Output is correct
6 Correct 5174 ms 35620 KB Output is correct
7 Correct 5088 ms 35612 KB Output is correct
8 Correct 12 ms 14028 KB Output is correct
9 Correct 11 ms 14028 KB Output is correct
10 Correct 4954 ms 34372 KB Output is correct
11 Correct 2715 ms 35732 KB Output is correct
12 Correct 1714 ms 23052 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 18736 KB Output is correct
2 Correct 87 ms 18756 KB Output is correct
3 Correct 78 ms 18864 KB Output is correct
4 Correct 70 ms 18892 KB Output is correct
5 Correct 70 ms 17716 KB Output is correct
6 Correct 17 ms 14180 KB Output is correct
7 Correct 1847 ms 28812 KB Output is correct
8 Correct 1884 ms 28672 KB Output is correct
9 Correct 71 ms 18872 KB Output is correct
10 Correct 1660 ms 27132 KB Output is correct
11 Correct 1566 ms 26728 KB Output is correct
12 Correct 660 ms 24064 KB Output is correct
13 Correct 613 ms 22320 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 18736 KB Output is correct
2 Correct 87 ms 18756 KB Output is correct
3 Correct 78 ms 18864 KB Output is correct
4 Correct 70 ms 18892 KB Output is correct
5 Correct 70 ms 17716 KB Output is correct
6 Correct 17 ms 14180 KB Output is correct
7 Correct 2737 ms 38820 KB Output is correct
8 Correct 2783 ms 38812 KB Output is correct
9 Correct 65 ms 18736 KB Output is correct
10 Correct 2800 ms 38692 KB Output is correct
11 Correct 2966 ms 38868 KB Output is correct
12 Correct 2868 ms 38820 KB Output is correct
13 Correct 2906 ms 38004 KB Output is correct
14 Correct 5372 ms 35616 KB Output is correct
15 Correct 5370 ms 35628 KB Output is correct
16 Correct 11 ms 14028 KB Output is correct
17 Correct 2582 ms 35612 KB Output is correct
18 Correct 1747 ms 23060 KB Output is correct
19 Correct 5174 ms 35620 KB Output is correct
20 Correct 5088 ms 35612 KB Output is correct
21 Correct 12 ms 14028 KB Output is correct
22 Correct 11 ms 14028 KB Output is correct
23 Correct 4954 ms 34372 KB Output is correct
24 Correct 2715 ms 35732 KB Output is correct
25 Correct 1714 ms 23052 KB Output is correct
26 Correct 1847 ms 28812 KB Output is correct
27 Correct 1884 ms 28672 KB Output is correct
28 Correct 71 ms 18872 KB Output is correct
29 Correct 1660 ms 27132 KB Output is correct
30 Correct 1566 ms 26728 KB Output is correct
31 Correct 660 ms 24064 KB Output is correct
32 Correct 613 ms 22320 KB Output is correct
33 Correct 6022 ms 44628 KB Output is correct
34 Correct 6082 ms 44660 KB Output is correct
35 Correct 4847 ms 40240 KB Output is correct
36 Correct 1598 ms 31472 KB Output is correct
37 Correct 1665 ms 31404 KB Output is correct
38 Correct 1773 ms 31572 KB Output is correct