oj.uz

답안 #53307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53307 2018-06-29T08:42:01 Z kinghsoo01(#1975) 섬 항해 (CEOI13_adriatic) C++11
100 / 100
 644 ms 153772 KB 
#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

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 147448 KB Output is correct
2 Correct 300 ms 147692 KB Output is correct
3 Correct 305 ms 147692 KB Output is correct
4 Correct 278 ms 147760 KB Output is correct
5 Correct 327 ms 147812 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 147812 KB Output is correct
2 Correct 291 ms 147944 KB Output is correct
3 Correct 294 ms 147944 KB Output is correct
4 Correct 277 ms 147944 KB Output is correct
5 Correct 288 ms 147944 KB Output is correct
6 Correct 339 ms 147944 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 147944 KB Output is correct
2 Correct 286 ms 147952 KB Output is correct
3 Correct 302 ms 147964 KB Output is correct
4 Correct 277 ms 147964 KB Output is correct
5 Correct 263 ms 147964 KB Output is correct
6 Correct 467 ms 147964 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 148400 KB Output is correct
2 Correct 396 ms 148400 KB Output is correct
3 Correct 348 ms 148400 KB Output is correct
4 Correct 288 ms 148448 KB Output is correct
5 Correct 309 ms 148448 KB Output is correct
6 Correct 508 ms 148600 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 637 ms 153772 KB Output is correct
2 Correct 493 ms 153772 KB Output is correct
3 Correct 531 ms 153772 KB Output is correct
4 Correct 491 ms 153772 KB Output is correct
5 Correct 426 ms 153772 KB Output is correct
6 Correct 558 ms 153772 KB Output is correct
7 Correct 644 ms 153772 KB Output is correct