Submission #53326

#	Time	Username	Problem	Language	Result	Execution time	Memory
53326		sebinkim	Adriatic (CEOI13_adriatic)	C++14	60 / 100	2073 ms	126508 KiB

adriatic

#include <bits/stdc++.h>

using namespace std;

int D[2525][2525];
int UX[2525][2525], UY[2525][2525];
int DX[2525][2525], DY[2525][2525];
int X[252525], Y[252525];
int n;

int sum(int x1,int y1,int x2,int y2)
{
	return D[x2][y2] - D[x2][y1-1] - D[x1-1][y2] + D[x1-1][y1-1];
}

int main()
{
	int i,j;
	int x1,x2,y1,y2;
	int x1_,x2_,y1_,y2_;
	int ans,cnt,p;
	
	for(i=0;i<=2500;i++){
		for(j=0;j<=2500;j++){
			UX[i][j] = 1e9;
			UY[i][j] = 1e9;
		}
	}
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%d%d",X+i,Y+i);
		D[X[i]][Y[i]] ++;
		
		UX[X[i]][Y[i]] = X[i];
		UY[X[i]][Y[i]] = Y[i];
		DX[X[i]][Y[i]] = X[i];
		DY[X[i]][Y[i]] = Y[i];
	}
	
	for(i=1;i<=2500;i++){
		for(j=1;j<=2500;j++){
			D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1];
			UX[i][j] = min(min(UX[i-1][j], UX[i][j-1]), UX[i][j]);
			UY[i][j] = min(min(UY[i-1][j], UY[i][j-1]), UY[i][j]);
		}
	}
	
	for(i=2500;i>=1;i--){
		for(j=2500;j>=1;j--){
			DX[i][j] = max(max(DX[i+1][j], DX[i][j+1]), DX[i][j]);
			DY[i][j] = max(max(DY[i+1][j], DY[i][j+1]), DY[i][j]);
		}
	}
	
	for(i=0;i<n;i++){
		x1 = x2 = X[i];
		y1 = y2 = Y[i];
		
		cnt = 0;
		ans = 0;
		
		for(j=1;;j++){
			p = n-1 - sum(1, y2, x1, 2500) - sum(x2, 1, 2500, y1);
			if(j == 1) p += 2;
			
			if(p == cnt) break;
			
			x1_ = UX[x2-1][y2-1]; y1_ = UY[x2-1][y2-1];
			x2_ = DX[x1+1][y1+1]; y2_ = DY[x1+1][y1+1];
			
			x1 = min(x1, x1_); x2 = max(x2, x2_);
			y1 = min(y1, y1_); y2 = max(y2, y2_);
			
			ans += j * (p - cnt);
			cnt = p;
		}
		
		printf("%d\n",ans);
	}
	
	return 0;
}

Compilation message (stderr)

adriatic.cpp: In function 'int main()':
adriatic.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
adriatic.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",X+i,Y+i);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20