Submission #250226

#	Time	Username	Problem	Language	Result	Execution time	Memory
250226		errorgorn	Adriatic (CEOI13_adriatic)	C++14	100 / 100	266 ms	153700 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int n;
int arr[2505][2505];
int pre[2505][2505];

int top[2505];
int bottom[2505];
int l[2505];
int r[2505];

vector<ii> q;

long long memo1[2505][2505];
long long memo2[2505][2505];

long long dp1(int i,int j){
	if (memo1[i][j]!=-1) return memo1[i][j];
	int res=pre[2504][j]-pre[i-1][j];

	if (res==0) return memo1[i][j]=0;
	
	return memo1[i][j]=res+dp1(max(i,bottom[j+1]),min(j,l[i-1]));
}

long long dp2(int i,int j){
	if (memo2[i][j]!=-1) return memo2[i][j];
	int res=pre[i][2504]-pre[i][j-1];
	
	if (res==0) return memo2[i][j]=0;
	
	return memo2[i][j]=res+dp2(min(i,top[j-1]),max(j,r[i+1]));
}

int main(){
	memset(top,127,sizeof(top));
	memset(bottom,-1,sizeof(bottom));
	memset(l,127,sizeof(l));
	memset(r,-1,sizeof(r));

	memset(memo1,-1,sizeof(memo1));
	memset(memo2,-1,sizeof(memo2));
	
	scanf("%d",&n);
	
	int a,b;
	for (int x=0;x<n;x++){
		scanf("%d%d",&a,&b);
		arr[a][b]=1;
		
		top[b]=min(top[b],a);
		bottom[b]=max(bottom[b],a);
		l[a]=min(l[a],b);
		r[a]=max(r[a],b);
		
		q.push_back(ii(a,b));
	}
	
	for (int x=1;x<2505;x++){
		top[x]=min(top[x],top[x-1]);
		l[x]=min(l[x],l[x-1]);
	}
	
	for (int x=2503;~x;x--){
		bottom[x]=max(bottom[x],bottom[x+1]);
		r[x]=max(r[x],r[x+1]);
	}
	
	for (int x=1;x<2505;x++){
		for (int y=1;y<2505;y++){
			pre[x][y]=pre[x-1][y]+pre[x][y-1]-pre[x-1][y-1]+arr[x][y];
		}
	}
	
	for (auto &it:q){
		printf("%lld\n",dp1(it.first,it.second)+dp2(it.first,it.second)+n-3);
	}
}

Compilation message (stderr)

adriatic.cpp: In function 'int main()':
adriatic.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
adriatic.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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