Submission #930227

#	Time	Username	Problem	Language	Result	Execution time	Memory
930227		tamir1	Adriatic (CEOI13_adriatic)	C++14	100 / 100	160 ms	156208 KiB

adriatic

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x[250005],y[250005],dp[2505][2505],i,j,L[2505],R[2505],U[2505],D[2505],ru[2505][2505],ld[2505][2505];
ll LD(ll x,ll y){
	ll &ret=ld[x][y];
	if(ret!=-1) return ret;
	ret=dp[2500][y]-dp[x-1][y];
	if(ret==0) return 0;
	ll X=max(x,D[y+1]);
	ll Y=min(y,L[x-1]);
	ret=ret+LD(X,Y);
	return ret;
}
ll RU(ll x,ll y){
	ll &ret=ru[x][y];
	if(ret!=-1) return ret;
	ret=dp[x][2500]-dp[x][y-1];
	if(ret==0) return 0;
	ll X=min(x,U[y-1]);
	ll Y=max(y,R[x+1]);
	ret=ret+RU(X,Y);
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(i=0;i<=2500;i++){
		U[i]=3000;
		L[i]=3000;
	}
	cin >> n;
	for(i=1;i<=n;i++){
		cin >> x[i] >> y[i];
		dp[x[i]][y[i]]=1;
		U[y[i]]=min(U[y[i]],x[i]);
		L[x[i]]=min(L[x[i]],y[i]);
		D[y[i]]=max(D[y[i]],x[i]);
		R[x[i]]=max(R[x[i]],y[i]);
	}
	for(i=1;i<=2500;i++){
		for(j=1;j<=2500;j++){
			dp[i][j]=dp[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			ld[i][j]=-1;
			ru[i][j]=-1;
		}
	}
	for(i=1;i<=2500;i++){
		L[i]=min(L[i],L[i-1]);
		U[i]=min(U[i],U[i-1]);
	}
	for(i=2500;i>=1;i--){
		R[i]=max(R[i],R[i+1]);
		D[i]=max(D[i],D[i+1]);
	}
	for(i=1;i<=n;i++){
		cout << LD(x[i],y[i])+RU(x[i],y[i])+n-3 << "\n";
	}
}

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