oj.uz

Submission #63164

# Submission time Handle Problem Language Result Execution time Memory
63164 2018-08-01T01:35:35 Z khsoo01 Adriatic (CEOI13_adriatic) C++11
100 / 100
 831 ms 171252 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

# Verdict Execution time Memory Grader output
1 Correct 351 ms 147652 KB Output is correct
2 Correct 332 ms 147652 KB Output is correct
3 Correct 346 ms 147672 KB Output is correct
4 Correct 347 ms 147816 KB Output is correct
5 Correct 338 ms 147824 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 147988 KB Output is correct
2 Correct 347 ms 148036 KB Output is correct
3 Correct 411 ms 148084 KB Output is correct
4 Correct 344 ms 148100 KB Output is correct
5 Correct 368 ms 148100 KB Output is correct
6 Correct 390 ms 148100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 148344 KB Output is correct
2 Correct 381 ms 148344 KB Output is correct
3 Correct 429 ms 148344 KB Output is correct
4 Correct 325 ms 148364 KB Output is correct
5 Correct 329 ms 148404 KB Output is correct
6 Correct 548 ms 148404 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 149264 KB Output is correct
2 Correct 410 ms 149364 KB Output is correct
3 Correct 452 ms 149668 KB Output is correct
4 Correct 399 ms 149684 KB Output is correct
5 Correct 368 ms 150000 KB Output is correct
6 Correct 628 ms 150292 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 157904 KB Output is correct
2 Correct 750 ms 159788 KB Output is correct
3 Correct 780 ms 162028 KB Output is correct
4 Correct 582 ms 163900 KB Output is correct
5 Correct 648 ms 166320 KB Output is correct
6 Correct 786 ms 168876 KB Output is correct
7 Correct 831 ms 171252 KB Output is correct