oj.uz

Submission #439717

# Submission time Handle Problem Language Result Execution time Memory
439717 2021-06-30T16:08:02 Z kig9981 Road Construction (JOI21_road_construction) C++17
33 / 100
 5442 ms 41924 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]) 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())-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() && i!=P[m][j]) 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]) add_tree(u,k);
		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);
	}
	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:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j=0;j<P[m].size();j++) {
      |               ~^~~~~~~~~~~~
road_construction.cpp:56:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    while(j<P[m].size() && 1LL*abs(X[P[m][j]]-X[i])+abs(Y[P[m][j]]-Y[i])>K) {
      |          ~^~~~~~~~~~~~
road_construction.cpp:61:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    if(j<P[m].size() && i!=P[m][j]) 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:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=0;i<x.size();i++) {
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:106:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  while(ans.size()<K) ans.push_back(s);
      |        ~~~~~~~~~~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18764 KB Output is correct
2 Correct 85 ms 18824 KB Output is correct
3 Correct 75 ms 18864 KB Output is correct
4 Correct 72 ms 18828 KB Output is correct
5 Incorrect 77 ms 17712 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2747 ms 38736 KB Output is correct
2 Correct 2819 ms 41824 KB Output is correct
3 Correct 66 ms 18700 KB Output is correct
4 Correct 2782 ms 41648 KB Output is correct
5 Correct 2923 ms 41744 KB Output is correct
6 Correct 2851 ms 41924 KB Output is correct
7 Correct 2857 ms 41204 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5382 ms 35616 KB Output is correct
2 Correct 5360 ms 40700 KB Output is correct
3 Correct 12 ms 14104 KB Output is correct
4 Correct 2791 ms 38520 KB Output is correct
5 Correct 1824 ms 28452 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5382 ms 35616 KB Output is correct
2 Correct 5360 ms 40700 KB Output is correct
3 Correct 12 ms 14104 KB Output is correct
4 Correct 2791 ms 38520 KB Output is correct
5 Correct 1824 ms 28452 KB Output is correct
6 Correct 5411 ms 40696 KB Output is correct
7 Correct 5442 ms 40692 KB Output is correct
8 Correct 12 ms 14028 KB Output is correct
9 Correct 12 ms 14028 KB Output is correct
10 Correct 5095 ms 39560 KB Output is correct
11 Correct 2887 ms 38560 KB Output is correct
12 Correct 1831 ms 28404 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18764 KB Output is correct
2 Correct 85 ms 18824 KB Output is correct
3 Correct 75 ms 18864 KB Output is correct
4 Correct 72 ms 18828 KB Output is correct
5 Incorrect 77 ms 17712 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18764 KB Output is correct
2 Correct 85 ms 18824 KB Output is correct
3 Correct 75 ms 18864 KB Output is correct
4 Correct 72 ms 18828 KB Output is correct
5 Incorrect 77 ms 17712 KB Output isn't correct
6 Halted 0 ms 0 KB -