oj.uz

Submission #53326

# Submission time Handle Problem Language Result Execution time Memory
53326 2018-06-29T09:54:09 Z sebinkim Adriatic (CEOI13_adriatic) C++14
60 / 100
 2000 ms 126508 KB 
#include <bits/stdc++.h>

using namespace std;

int D[2525][2525];
int UX[2525][2525], UY[2525][2525];
int DX[2525][2525], DY[2525][2525];
int X[252525], Y[252525];
int n;

int sum(int x1,int y1,int x2,int y2)
{
	return D[x2][y2] - D[x2][y1-1] - D[x1-1][y2] + D[x1-1][y1-1];
}

int main()
{
	int i,j;
	int x1,x2,y1,y2;
	int x1_,x2_,y1_,y2_;
	int ans,cnt,p;
	
	for(i=0;i<=2500;i++){
		for(j=0;j<=2500;j++){
			UX[i][j] = 1e9;
			UY[i][j] = 1e9;
		}
	}
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%d%d",X+i,Y+i);
		D[X[i]][Y[i]] ++;
		
		UX[X[i]][Y[i]] = X[i];
		UY[X[i]][Y[i]] = Y[i];
		DX[X[i]][Y[i]] = X[i];
		DY[X[i]][Y[i]] = Y[i];
	}
	
	for(i=1;i<=2500;i++){
		for(j=1;j<=2500;j++){
			D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1];
			UX[i][j] = min(min(UX[i-1][j], UX[i][j-1]), UX[i][j]);
			UY[i][j] = min(min(UY[i-1][j], UY[i][j-1]), UY[i][j]);
		}
	}
	
	for(i=2500;i>=1;i--){
		for(j=2500;j>=1;j--){
			DX[i][j] = max(max(DX[i+1][j], DX[i][j+1]), DX[i][j]);
			DY[i][j] = max(max(DY[i+1][j], DY[i][j+1]), DY[i][j]);
		}
	}
	
	for(i=0;i<n;i++){
		x1 = x2 = X[i];
		y1 = y2 = Y[i];
		
		cnt = 0;
		ans = 0;
		
		for(j=1;;j++){
			p = n-1 - sum(1, y2, x1, 2500) - sum(x2, 1, 2500, y1);
			if(j == 1) p += 2;
			
			if(p == cnt) break;
			
			x1_ = UX[x2-1][y2-1]; y1_ = UY[x2-1][y2-1];
			x2_ = DX[x1+1][y1+1]; y2_ = DY[x1+1][y1+1];
			
			x1 = min(x1, x1_); x2 = max(x2, x2_);
			y1 = min(y1, y1_); y2 = max(y2, y2_);
			
			ans += j * (p - cnt);
			cnt = p;
		}
		
		printf("%d\n",ans);
	}
	
	return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 123972 KB Output is correct
2 Correct 157 ms 123972 KB Output is correct
3 Correct 158 ms 123972 KB Output is correct
4 Correct 159 ms 124092 KB Output is correct
5 Correct 155 ms 124136 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 124136 KB Output is correct
2 Correct 209 ms 124192 KB Output is correct
3 Correct 161 ms 124192 KB Output is correct
4 Correct 173 ms 124252 KB Output is correct
5 Correct 179 ms 124252 KB Output is correct
6 Correct 259 ms 124252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 124304 KB Output is correct
2 Correct 163 ms 124480 KB Output is correct
3 Correct 201 ms 124480 KB Output is correct
4 Correct 173 ms 124480 KB Output is correct
5 Correct 174 ms 124480 KB Output is correct
6 Correct 908 ms 124500 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1551 ms 124924 KB Output is correct
2 Correct 171 ms 124924 KB Output is correct
3 Correct 245 ms 124924 KB Output is correct
4 Correct 170 ms 124924 KB Output is correct
5 Correct 174 ms 124924 KB Output is correct
6 Execution timed out 2073 ms 124924 KB Time limit exceeded

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 126508 KB Time limit exceeded
2 Halted 0 ms 0 KB -