Submission #288709

#	Time	Username	Problem	Language	Result	Execution time	Memory
288709		TadijaSebez	Adriatic (CEOI13_adriatic)	C++11	100 / 100	251 ms	80376 KiB

adriatic

#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 (stderr)

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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20