Submission #352660

#	Time	Username	Problem	Language	Result	Execution time	Memory
352660		arnold518	Kosta (COI14_kosta)	C++14	100 / 100	1600 ms	24144 KiB

kosta

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

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

#define x first
#define y second

const int MAXN = 2e5;
const int INF = 2e8;

int N, K;
pii A[MAXN+10];

int D;
int ans1, ans2;

int XL[MAXN+10], XR[MAXN+10], YL[MAXN+10], YR[MAXN+10], C[MAXN+10];

struct BIT
{
	int tree[4000010];
	void init()
	{
		memset(tree, 0, sizeof(tree));
	}
	void update(int i)
	{
		for(i+=2000001; i<=4000001; i+=(i&-i)) tree[i]++;
	}
	int query(int i)
	{
		int ret=0;
		for(i+=2000001; i>0; i-=(i&-i)) ret+=tree[i];
		return ret;
	}
}bit;

bool solve(int _D)
{
	D=_D;
	//printf("SOLVE %d\n", D);

	for(int i=1; i<=N; i++)
	{
		XL[i]=INF;
		XR[i]=-INF;
		YL[i]=INF;
		YR[i]=-INF;
	}

	{
		vector<pii> V, V2;
		for(int i=1; i<=N; i++) V.push_back({A[i].x-D, i});
		for(int i=1; i<=N; i++) V2.push_back(A[i]);
		sort(V.begin(), V.end());
		sort(V2.begin(), V2.end());

		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=0, j=0; i<V.size(); i++)
		{
			for(; j<V2.size() && V2[j].x<V[i].x; j++)
			{
				xl=min(xl, V2[j].x);
				xr=max(xr, V2[j].x);
				yl=min(yl, V2[j].y);
				yr=max(yr, V2[j].y);
			}
			int it=V[i].second;
			XL[it]=min(XL[it], xl);
			XR[it]=max(XR[it], xr);
			YL[it]=min(YL[it], yl);
			YR[it]=max(YR[it], yr);
		}	
	}
	{
		vector<pii> V, V2;
		for(int i=1; i<=N; i++) V.push_back({A[i].x+D, i});
		for(int i=1; i<=N; i++) V2.push_back(A[i]);
		sort(V.begin(), V.end(), greater<pii>());
		sort(V2.begin(), V2.end(), greater<pii>());

		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=0, j=0; i<V.size(); i++)
		{
			for(; j<V2.size() && V2[j].x>V[i].x; j++)
			{
				xl=min(xl, V2[j].x);
				xr=max(xr, V2[j].x);
				yl=min(yl, V2[j].y);
				yr=max(yr, V2[j].y);
			}
			int it=V[i].second;
			XL[it]=min(XL[it], xl);
			XR[it]=max(XR[it], xr);
			YL[it]=min(YL[it], yl);
			YR[it]=max(YR[it], yr);
		}	
	}
	{
		vector<pii> V, V2;
		for(int i=1; i<=N; i++) V.push_back({A[i].y-D, i});
		for(int i=1; i<=N; i++) V2.push_back({A[i].y, A[i].x});
		sort(V.begin(), V.end());
		sort(V2.begin(), V2.end());

		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=0, j=0; i<V.size(); i++)
		{
			for(; j<V2.size() && V2[j].x<V[i].x; j++)
			{
				xl=min(xl, V2[j].y);
				xr=max(xr, V2[j].y);
				yl=min(yl, V2[j].x);
				yr=max(yr, V2[j].x);
			}
			int it=V[i].second;
			XL[it]=min(XL[it], xl);
			XR[it]=max(XR[it], xr);
			YL[it]=min(YL[it], yl);
			YR[it]=max(YR[it], yr);
		}	
	}
	{
		vector<pii> V, V2;
		for(int i=1; i<=N; i++) V.push_back({A[i].y+D, i});
		for(int i=1; i<=N; i++) V2.push_back({A[i].y, A[i].x});
		sort(V.begin(), V.end(), greater<pii>());
		sort(V2.begin(), V2.end(), greater<pii>());

		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=0, j=0; i<V.size(); i++)
		{
			for(; j<V2.size() && V2[j].x>V[i].x; j++)
			{
				xl=min(xl, V2[j].y);
				xr=max(xr, V2[j].y);
				yl=min(yl, V2[j].x);
				yr=max(yr, V2[j].x);
			}
			int it=V[i].second;
			XL[it]=min(XL[it], xl);
			XR[it]=max(XR[it], xr);
			YL[it]=min(YL[it], yl);
			YR[it]=max(YR[it], yr);
		}	
	}
	vector<pair<pii, int>> VV;
	vector<pii> V2;

	for(int i=1; i<=N; i++) V2.push_back(A[i]);
	sort(V2.begin(), V2.end());
	for(int i=1; i<=N; i++)
	{
		if(XL[i]==INF)
		{
			ans1=i; ans2=i;
			return true;
		}
		int xl, xr, yl, yr;
		xl=XR[i]-D; xr=XL[i]+D;
		yl=YR[i]-D; yr=YL[i]+D;

		if(xl>xr) continue;
		if(yl>yr) continue;
		//printf("%d : %d %d %d %d\n", i, xl, xr, yl, yr);

		VV.push_back({{xr, yr}, i});
		VV.push_back({{xl-1, yr}, -i});
		VV.push_back({{xr, yl-1}, -i});
		VV.push_back({{xl-1, yl-1}, i});
	}
	sort(VV.begin(), VV.end());

	bit.init();
	for(int i=1; i<=N; i++) C[i]=0;

	for(int i=0, j=0; i<VV.size(); i++)
	{
		for(; j<V2.size() && V2[j].x<=VV[i].first.x; j++)
		{
			bit.update(V2[j].y);
		}
		int t=VV[i].second;
		if(t>0) C[t]+=bit.query(VV[i].first.y);
		else C[-t]-=bit.query(VV[i].first.y);
	}

	//for(int j=1; j<=N; j++) printf("%d ", C[j]); printf("\n");

	//printf("HI\n");
	for(int j=1; j<=N; j++)
	{
		if(C[j]==0) continue;
		//printf("WOW %d %d\n", j, C[j]);
		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=1; i<=N; i++)
		{
			if(max({A[j].x-A[i].x, A[i].x-A[j].x, A[j].y-A[i].y, A[i].y-A[j].y})<=D) continue;
			xl=min(xl, A[i].x);
			xr=max(xr, A[i].x);
			yl=min(yl, A[i].y);
			yr=max(yr, A[i].y);
		}
		if(xl==INF)
		{
			ans1=ans2=j;
			return true;
		}
		for(int i=1; i<=N; i++)
		{
			int t=max({xr-A[i].x, A[i].x-xl, yr-A[i].y, A[i].y-yl});
			if(t<=D)
			{
				ans1=j; ans2=i;
				return true;
			}
		}
		assert(0);
	}

	return false;
}

int main()
{
	scanf("%d%d", &K, &N);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].x, &A[i].y);
		int x2=A[i].x+A[i].y;
		int y2=A[i].x-A[i].y;
		A[i]={x2, y2};
	}

	if(K==1)
	{
		int xl, xr, yl, yr;
		xl=INF; xr=-INF; yl=INF; yr=-INF;
		for(int i=1; i<=N; i++)
		{
			xl=min(xl, A[i].x);
			xr=max(xr, A[i].x);
			yl=min(yl, A[i].y);
			yr=max(yr, A[i].y);
		}
		int D=INF, ans=-1;
		for(int i=1; i<=N; i++)
		{
			int t=max({xr-A[i].x, A[i].x-xl, yr-A[i].y, A[i].y-yl});
			if(D>=t) D=t, ans=i;
		}
		printf("%d\n%d\n", D, ans);
	}
	else
	{
		int lo=0, hi=INF;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(solve(mid)) hi=mid;
			else lo=mid;
		}
		solve(hi);
		printf("%d\n%d %d\n", hi, ans1, ans2);
	}
}

Compilation message (stderr)

kosta.cpp: In function 'bool solve(int)':
kosta.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i=0, j=0; i<V.size(); i++)
      |                     ~^~~~~~~~~
kosta.cpp:65:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(; j<V2.size() && V2[j].x<V[i].x; j++)
      |          ~^~~~~~~~~~
kosta.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i=0, j=0; i<V.size(); i++)
      |                     ~^~~~~~~~~
kosta.cpp:90:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for(; j<V2.size() && V2[j].x>V[i].x; j++)
      |          ~^~~~~~~~~~
kosta.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i=0, j=0; i<V.size(); i++)
      |                     ~^~~~~~~~~
kosta.cpp:115:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |    for(; j<V2.size() && V2[j].x<V[i].x; j++)
      |          ~^~~~~~~~~~
kosta.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i=0, j=0; i<V.size(); i++)
      |                     ~^~~~~~~~~
kosta.cpp:140:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |    for(; j<V2.size() && V2[j].x>V[i].x; j++)
      |          ~^~~~~~~~~~
kosta.cpp:184:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |  for(int i=0, j=0; i<VV.size(); i++)
      |                    ~^~~~~~~~~~
kosta.cpp:186:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |   for(; j<V2.size() && V2[j].x<=VV[i].first.x; j++)
      |         ~^~~~~~~~~~
kosta.cpp: In function 'int main()':
kosta.cpp:267:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  267 |    int mid=lo+hi>>1;
      |            ~~^~~
kosta.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  234 |  scanf("%d%d", &K, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~
kosta.cpp:237:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  237 |   scanf("%d%d", &A[i].x, &A[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 2 / 2
• Subtask 6: 2 / 2
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 26 / 26
• Subtask 10: 26 / 26