oj.uz

Submission #250226

# Submission time Handle Problem Language Result Execution time Memory
250226 2020-07-17T08:55:36 Z errorgorn Adriatic (CEOI13_adriatic) C++14
100 / 100
 266 ms 153700 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 123640 KB Output is correct
2 Correct 85 ms 123640 KB Output is correct
3 Correct 84 ms 123640 KB Output is correct
4 Correct 84 ms 123372 KB Output is correct
5 Correct 85 ms 123384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 127736 KB Output is correct
2 Correct 88 ms 128504 KB Output is correct
3 Correct 86 ms 127864 KB Output is correct
4 Correct 87 ms 123640 KB Output is correct
5 Correct 86 ms 124024 KB Output is correct
6 Correct 89 ms 125944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 131836 KB Output is correct
2 Correct 95 ms 136952 KB Output is correct
3 Correct 91 ms 132216 KB Output is correct
4 Correct 90 ms 124920 KB Output is correct
5 Correct 87 ms 124536 KB Output is correct
6 Correct 90 ms 133496 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 134516 KB Output is correct
2 Correct 118 ms 147972 KB Output is correct
3 Correct 105 ms 134772 KB Output is correct
4 Correct 101 ms 126836 KB Output is correct
5 Correct 101 ms 126196 KB Output is correct
6 Correct 103 ms 134388 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 140516 KB Output is correct
2 Correct 250 ms 153700 KB Output is correct
3 Correct 266 ms 148200 KB Output is correct
4 Correct 222 ms 136804 KB Output is correct
5 Correct 200 ms 133864 KB Output is correct
6 Correct 220 ms 142052 KB Output is correct
7 Correct 212 ms 141668 KB Output is correct