oj.uz

Submission #288709

# Submission time Handle Problem Language Result Execution time Memory
288709 2020-09-01T19:26:27 Z TadijaSebez Adriatic (CEOI13_adriatic) C++11
100 / 100
 251 ms 80376 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=2505;
const int M=250050;
int l[N],r[N],u[N],d[N],sum[N][N],x[M],y[M],dp1[N][N],dp2[N][N];
int main(){
	int n;scanf("%i",&n);
	for(int i=0;i<N;i++)l[i]=u[i]=N-1;
	for(int i=1;i<=n;i++){
		scanf("%i %i",&x[i],&y[i]);
		sum[x[i]][y[i]]=1;
		l[x[i]]=min(l[x[i]],y[i]);
		u[y[i]]=min(u[y[i]],x[i]);
		r[x[i]]=max(r[x[i]],y[i]);
		d[y[i]]=max(d[y[i]],x[i]);
	}
	for(int i=1;i<N;i++)for(int j=1;j<N;j++)sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
	for(int i=1;i<N;i++)l[i]=min(l[i],l[i-1]),u[i]=min(u[i],u[i-1]);
	for(int i=N-2;i;i--)r[i]=max(r[i],r[i+1]),d[i]=max(d[i],d[i+1]);
	for(int i=N-3;i>=1;i--)for(int j=1;j<N-2;j++){
		int o=max(i,d[j+1]),p=min(j,l[i-1]);
		dp1[i][j]=dp1[o][p]+sum[N-1][j]-sum[i-1][j];
	}
	for(int i=1;i<N-2;i++)for(int j=N-3;j>=1;j--){
		int o=min(i,u[j-1]),p=max(j,r[i+1]);
		dp2[i][j]=dp2[o][p]+sum[i][N-1]-sum[i][j-1];
	}
	for(int i=1;i<=n;i++)printf("%i\n",dp1[x[i]][y[i]]+dp2[x[i]][y[i]]+n-3);
	return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 73980 KB Output is correct
2 Correct 84 ms 73976 KB Output is correct
3 Correct 90 ms 74008 KB Output is correct
4 Correct 88 ms 73980 KB Output is correct
5 Correct 90 ms 74036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 74104 KB Output is correct
2 Correct 90 ms 73976 KB Output is correct
3 Correct 99 ms 73976 KB Output is correct
4 Correct 88 ms 73976 KB Output is correct
5 Correct 87 ms 74020 KB Output is correct
6 Correct 92 ms 73976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 74104 KB Output is correct
2 Correct 86 ms 74104 KB Output is correct
3 Correct 93 ms 74104 KB Output is correct
4 Correct 96 ms 74104 KB Output is correct
5 Correct 89 ms 74104 KB Output is correct
6 Correct 124 ms 74104 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 74620 KB Output is correct
2 Correct 98 ms 74616 KB Output is correct
3 Correct 104 ms 74588 KB Output is correct
4 Correct 97 ms 74488 KB Output is correct
5 Correct 96 ms 74616 KB Output is correct
6 Correct 129 ms 74616 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 80124 KB Output is correct
2 Correct 244 ms 79968 KB Output is correct
3 Correct 251 ms 79992 KB Output is correct
4 Correct 212 ms 79624 KB Output is correct
5 Correct 205 ms 80104 KB Output is correct
6 Correct 243 ms 80076 KB Output is correct
7 Correct 217 ms 80376 KB Output is correct