Submission #63164

#	Time	Username	Problem	Language	Result	Execution time	Memory
63164		khsoo01	Adriatic (CEOI13_adriatic)	C++11	100 / 100	831 ms	171252 KiB

adriatic

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 250005, M = 2500, inf = 1e18;
ll n, x[N], y[N], s[M+5][M+5], u[M+5], d[M+5], r[M+5], l[M+5];
ll ru[M+5][M+5], ld[M+5][M+5];

ll val (ll XS, ll XE, ll YS, ll YE) {
	return s[XE][YE] - s[XS-1][YE] - s[XE][YS-1] + s[XS-1][YS-1];
}

int main ()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&x[i],&y[i]);
		s[x[i]][y[i]]++;
	}
	l[0] = u[0] = inf;
	for(ll i=1;i<=M;i++) {
		l[i] = l[i-1];
		u[i] = u[i-1];
		for(ll j=1;j<=M;j++) {
			if(s[i][j] && j < l[i]) l[i] = j;
			if(s[j][i] && j < u[i]) u[i] = j;
		}
	}
	r[M+1] = d[M+1] = -inf;
	for(ll i=M;i>=1;i--) {
		r[i] = r[i+1];
		d[i] = d[i+1];
		for(ll j=1;j<=M;j++) {
			if(s[i][j] && j > r[i]) r[i] = j;
			if(s[j][i] && j > d[i]) d[i] = j;
		}
	}
	for(ll i=1;i<=M;i++) {
		for(ll j=1;j<=M;j++) {
			s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
		}
	}
	for(ll i=M;i>=1;i--) {
		for(ll j=1;j<=M;j++) {
			ll X = max(d[j+1], i), Y = min(l[i-1], j);
			ld[i][j] = 2 * val(i,M,1,j) - val(X,M,1,Y) + ld[X][Y];
		}
	}
	for(ll i=1;i<=M;i++) {
		for(ll j=M;j>=1;j--) {
			ll X = min(u[j-1], i), Y = max(r[i+1], j);
			ru[i][j] = 2 * val(1,i,j,M) - val(1,X,Y,M) + ru[X][Y];
		}
	}
	for(ll i=1;i<=n;i++) {
		int A = x[i], B = y[i];
		printf("%lld\n",ld[A][B]+ru[A][B]-4+val(1,A-1,1,B-1)+val(A+1,M,B+1,M));
	}
}

Compilation message (stderr)

adriatic.cpp: In function 'int main()':
adriatic.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
adriatic.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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