#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
const int L = 2500;
struct Point{
int x, y, idx;
Point(){}
Point(int x, int y, int idx): x(x), y(y), idx(idx){}
};
void input();
void solve();
int n;
Point arr[250002];
ll ans;
int main(){
input();
solve();
}
void input(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
arr[i].idx = i;
}
}
int sum[L+2][L+2]; /// 구간 합
int minI[L+2][L+2]; /// [1, i] [1, j] 에서 최소 i
int maxI[L+2][L+2]; /// [1, i] [1, j] 에서 최대 i
int minJ[L+2][L+2]; /// [i, L] [j, L] 에서 최소 j
int maxJ[L+2][L+2]; /// [i, L] [j, L] 에서 최대 j
int rectSum(int xl, int yl, int xr, int yr){
xl = max(xl, 1), yl = max(yl, 1);
xr = min(xr, L), yr = min(yr, L);
if(xl>xr || yl>yr) return 0;
return sum[xr][yr] - sum[xl-1][yr] - sum[xr][yl-1] + sum[xl-1][yl-1];
}
ll DP1[L+2][L+2]; /// i증가, j감소방향 거리
ll DP2[L+2][L+2]; /// i감소, j증가방향 거리
void solve(){
for(int i=0; i<=L+1; i++) for(int j=0; j<=L+1; j++){
minI[i][j] = minJ[i][j] = L+1;
maxI[i][j] = maxJ[i][j] = 0;
}
for(int i=1; i<=n; i++){
sum[arr[i].x][arr[i].y] = 1;
minI[arr[i].x][arr[i].y] = maxI[arr[i].x][arr[i].y] = arr[i].x;
minJ[arr[i].x][arr[i].y] = maxJ[arr[i].x][arr[i].y] = arr[i].y;
}
for(int i=1; i<=L+1; i++){
for(int j=1; j<=L+1; j++){
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
minI[i][j] = min({minI[i][j], minI[i-1][j], minI[i][j-1]});
minJ[i][j] = min({minJ[i][j], minJ[i-1][j], minJ[i][j-1]});
}
}
for(int i=L; i>=0; i--){
for(int j=L; j>=0; j--){
maxI[i][j] = max({maxI[i][j], maxI[i+1][j], maxI[i][j+1]});
maxJ[i][j] = max({maxJ[i][j], maxJ[i+1][j], maxJ[i][j+1]});
}
}
/// DP1. maxI, minJ 활용
for(int j=1; j<=L; j++){
for(int i=L; i>=1; i--){
int ti = max(maxI[i+1][j+1], i);
int tj = min(minJ[i-1][j-1], j);
/**
tj
1 2 3 O
4 5 6 7
8 9 10 11 ti
12 13 14 15 */
/// 더 왼쪽 아래 부분 (8 9 12 13)
if(ti<=L && tj>0) DP1[i][j] += DP1[max(ti, i+1)][min(tj, j-1)] + rectSum(max(ti, i+1), 1, L, min(tj, j-1));
/// 4 5 6 10 14는 두 번에 이동 가능
DP1[i][j] += (rectSum(i+1, 1, L, j-1) - rectSum(max(ti, i+1), 1, L, min(tj, j-1))) * 2;
/// 1 2 3은 casework
if(ti != i) DP1[i][j] += rectSum(i, 1, i, j-1) * 2;
else DP1[i][j] += rectSum(i, 1, i, tj) * 3 + rectSum(i, tj+1, i, j-1) * 2;
/// 7 11 15도 casework
if(tj != j) DP1[i][j] += rectSum(i+1, j, L, j) * 2;
else DP1[i][j] += rectSum(i+1, j, ti-1, j) * 2 + rectSum(ti, j, L, j) * 3;
// printf("DP1 %d %d: %lld\n", i, j, DP1[i][j]);
}
}
/// DP2. minI, maxJ 활용
for(int i=1; i<=L; i++){
for(int j=L; j>=1; j--){
int ti = min(minI[i-1][j-1], i);
int tj = max(maxJ[i+1][j+1], j);
/**
tj
1 2 3 4
5 6 7 8 ti
9 10 11 12
O 13 14 15 */
/// 더 오른쪽 위 부분 (3 4 7 8)
if(ti>0 && tj<=L) DP2[i][j] += DP2[min(ti, i-1)][max(tj, j+1)] + rectSum(1, max(tj, j+1), min(ti, i-1), L);
/// 2 6 10 11 12는 두 번에 이동 가능
DP2[i][j] += (rectSum(1, j+1, i-1, L) - rectSum(1, max(tj, j+1), min(ti, i-1), L)) * 2;
/// 13 14 15는 casework
if(ti != i) DP2[i][j] += rectSum(i, j+1, i, L) * 2;
else DP2[i][j] += rectSum(i, j+1, i, tj-1) * 2 + rectSum(i, tj, i, L) * 3;
/// 1 5 9도 casework
if(tj != j) DP2[i][j] += rectSum(1, j, i-1, j) * 2;
else DP2[i][j] += rectSum(1, j, ti, j) * 3 + rectSum(ti+1, j, i-1, j) * 2;
// printf("DP2 %d %d: %lld\n", i, j, DP2[i][j]);
}
}
/// 답 출력
for(int i=1; i<=n; i++){
int x = arr[i].x, y = arr[i].y;
ans = DP1[x][y] + DP2[x][y] + rectSum(1, 1, x-1, y-1) + rectSum(x+1, y+1, L, L);
// printf("%d: %d %d %lld %lld\n", i, x, y, DP1[x][y], DP2[x][y]);
printf("%lld\n", ans);
}
}
Compilation message
adriatic.cpp: In function 'void input()':
adriatic.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
adriatic.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
748 ms |
220660 KB |
Output is correct |
| 2 |
Correct |
690 ms |
220636 KB |
Output is correct |
| 3 |
Correct |
738 ms |
220692 KB |
Output is correct |
| 4 |
Incorrect |
772 ms |
220712 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
764 ms |
220656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
749 ms |
220744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
836 ms |
221360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
863 ms |
227828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
