oj.uz

Submission #572905

# Submission time Handle Problem Language Result Execution time Memory
572905 2022-06-05T13:16:19 Z ftkbrian Adriatic (CEOI13_adriatic) C++14
0 / 100
 207 ms 108404 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll,ll>
#define x first
#define y second

ll n;
const ll len = 2500;
ll board[len+3][len+3],dp[len+3][len+3];
pll point[252525];
ll score[252525];
ll X_bgY[len+3],Y_smX[len+3];

ll box(ll sx,ll ex,ll sy,ll ey) {
	return board[ex][ey]-board[sx-1][ey]-board[ex][sy-1]+board[sx-1][sy-1];
}
ll reach(ll x,ll y) {
	return box(1,x-1,1,y-1)+box(x+1,len,y+1,len);
}

void init(ll cnt) {
	for(ll i = 0 ; i <= len+1 ; i++) X_bgY[i] = 0,Y_smX[i] = len+1;
	for(ll i = 0 ; i <= len+1 ; i++) for(ll q = 0 ; q <= len+1 ; q++) dp[i][q] = board[i][q] = 0;


	for(int i = 1 ; i <= n ; i++) {
		board[point[i].x][point[i].y] = 1;
		X_bgY[point[i].x] = max(X_bgY[point[i].x],point[i].y);
		Y_smX[point[i].y] = min(Y_smX[point[i].y],point[i].x);
	}


	for(int i = 1 ; i <= len ; i++)
		for(int q = 1 ; q <= len ; q++) 
			board[i][q] += board[i-1][q]+board[i][q-1]-board[i-1][q-1];

	if(cnt == 1) {
		for(int i = 1 ; i <= n ; i++)
			score[i] = reach(point[i].x,point[i].y);
	}


	for(int i = 1 ; i <= len ; i++) Y_smX[i] = min(Y_smX[i],Y_smX[i-1]);
	for(int i = len ; i >= 1 ; i--) X_bgY[i] = max(X_bgY[i],X_bgY[i+1]);
}

void solve(ll cnt) {
	init(cnt);

	for(ll x = 1 ; x <= len ; x++) {
		for(ll y = len ; y >= 1 ; y--) {
			ll nwX = min(x,Y_smX[y-1]);
			ll nwY = max(y,X_bgY[x+1]);
			dp[x][y] = box(1,x,y,len)-box(x,x,y,y)+dp[nwX][nwY];
		}
	}
	
	for(int i = 1 ; i <= n ; i++) {
		score[i] += dp[point[i].x][point[i].y]+box(1,point[i].x,point[i].y,len)-1;
	}
}

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n;
	for(int i = 1 ; i <= n ; i++) {
		cin>>point[i].x>>point[i].y;
	}
	solve(1);

	for(int i = 1 ; i <= n ; i++) {
		swap(point[i].x,point[i].y);
	}
	solve(2);

	for(int i = 1 ; i <= n ; i++) {
		cout<<score[i]<<"\n";
	}
}

Compilation message

adriatic.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main() {
      | ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 98496 KB Output is correct
2 Correct 114 ms 98384 KB Output is correct
3 Correct 112 ms 98416 KB Output is correct
4 Incorrect 114 ms 98412 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 98420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 98588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 99352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 108404 KB Output isn't correct
2 Halted 0 ms 0 KB -