oj.uz

Submission #930227

# Submission time Handle Problem Language Result Execution time Memory
930227 2024-02-19T06:37:30 Z tamir1 Adriatic (CEOI13_adriatic) C++14
100 / 100
 160 ms 156208 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 150348 KB Output is correct
2 Correct 39 ms 150312 KB Output is correct
3 Correct 39 ms 150324 KB Output is correct
4 Correct 47 ms 150356 KB Output is correct
5 Correct 37 ms 150304 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 150360 KB Output is correct
2 Correct 39 ms 150352 KB Output is correct
3 Correct 39 ms 150352 KB Output is correct
4 Correct 49 ms 150348 KB Output is correct
5 Correct 38 ms 150260 KB Output is correct
6 Correct 39 ms 150356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 150396 KB Output is correct
2 Correct 40 ms 150364 KB Output is correct
3 Correct 40 ms 150444 KB Output is correct
4 Correct 48 ms 150356 KB Output is correct
5 Correct 38 ms 150352 KB Output is correct
6 Correct 39 ms 150356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 150836 KB Output is correct
2 Correct 48 ms 150608 KB Output is correct
3 Correct 46 ms 150616 KB Output is correct
4 Correct 51 ms 150604 KB Output is correct
5 Correct 44 ms 150588 KB Output is correct
6 Correct 44 ms 150864 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 156028 KB Output is correct
2 Correct 156 ms 155736 KB Output is correct
3 Correct 160 ms 155688 KB Output is correct
4 Correct 127 ms 155292 KB Output is correct
5 Correct 108 ms 155872 KB Output is correct
6 Correct 109 ms 155912 KB Output is correct
7 Correct 116 ms 156208 KB Output is correct