#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
typedef pair <LL, int> LLI;
const int N = 3e5 + 10;
const int LG = 20;
const int A = 2500 + 10;
const int INF = 0x3f3f3f3f;
struct Point {
int x, y;
Point () {}
Point (int x, int y) : x(x), y(y) {}
} P[N];
int n, sx, sy;
int a[A + 10][A + 10], C1[A + 10][A + 10], C2[A + 10][A + 10];
int C3[A + 10][A + 10], C4[A + 10][A + 10];
int lg[A + 20];
struct RMQ {
int spT[2][N][LG + 3];
void Build() {
FOR(i, 0, 1)
FOR(j, 1, n) spT[i][j][0] = (i == 0 ? INF : -INF);
FOR(i, 0, 1)
FOR(j, 1, n) {
spT[i][P[j].x][0] = (i == 0) ? min(spT[i][P[j].x][0], P[j].y) :
max(spT[i][P[j].x][0], P[j].y);
}
for (int j = 1; 1 << j <= A; ++j)
for (int i = 1; i + (1 << j) - 1 <= A; ++i) {
spT[0][i][j] = min(spT[0][i][j - 1], spT[0][i + (1 << (j - 1))][j - 1]);
spT[1][i][j] = max(spT[1][i][j - 1], spT[1][i + (1 << (j - 1))][j - 1]);
}
}
int Query(int t, int l, int r) {
if (l > r) return (t == 0 ? INF : -INF);
int k = lg[r - l + 1];
if (t == 0) return min(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
else return max(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
}
} RMQX, RMQY;
void Init() {
for (int i = 0; 1 << i <= A; ++i) lg[1 << i] = i;
FOR(i, 1, A) if (!lg[i]) lg[i] = lg[i - 1];
RMQY.Build();
FOR(i, 1, n) swap(P[i].x, P[i].y);
RMQX.Build();
FOR(i, 1, n) swap(P[i].x, P[i].y);
FOR(i, 1, A)
FOD(j, A, 1) {
C1[i][j] = C1[i - 1][j] + C1[i][j + 1] - C1[i - 1][j + 1] + a[i][j];
}
FOD(i, A, 1)
FOR(j, 1, A) {
C2[i][j] = C2[i][j - 1] + C2[i + 1][j] - C2[i + 1][j - 1] + a[i][j];
}
FOR(i, 1, A)
FOR(j, 1, A)
C3[i][j] = C3[i][j - 1] + C3[i - 1][j] - C3[i - 1][j - 1] + a[i][j];
FOD(i, A, 1)
FOD(j, A, 1)
C4[i][j] = C4[i][j + 1] + C4[i + 1][j] - C4[i + 1][j + 1] + a[i][j];
}
LL ComputeUp(int level, int x, int y, int ly, int rx) {
if (C1[x][y] == 0) return 0;
int minX = RMQX.Query(0, ly, y - 1); minX = min(minX, x);
int maxY = RMQY.Query(1, x + 1, rx); maxY = max(maxY, y);
if (minX == x && maxY == y) return 0;
LL ans = level * (C1[x][y] - C1[minX][maxY] - (sx == x && sy == y));
return ans + ComputeUp(level + 1, minX, maxY, y, x);
}
LL ComputeDown(int level, int x, int y, int lx, int ry) {
if (C2[x][y] == 0) return 0;
int maxX = RMQX.Query(1, y + 1, ry); maxX = max(maxX, x);
int minY = RMQY.Query(0, lx, x - 1); minY = min(minY, y);
if (maxX == x && minY == y) return 0;
//DEBUG(x);
//DEBUG(y);
//cout << y + 1 << " " << ry << endl;
//cout << maxX << " " << minY << endl;
// cout << C2[x][y] - C2[maxX][minY] - (sx == x && sy == y) << endl;
LL ans = (LL)level * (C2[x][y] - C2[maxX][minY] - (sx == x && sy == y));
return ans + ComputeDown(level + 1, maxX, minY, x, y);
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d", &n);
FOR(i, 1, n) {
int x, y; scanf("%d%d", &x, &y);
P[i] = Point(x, y);
a[x][y] = 1;
}
Init();
FOR(i, 1, n) {
sx = P[i].x, sy = P[i].y;
LL up = ComputeUp(2, sx, sy, 1, A);
LL down = ComputeDown(2, sx, sy, 1, A);
//cout << up << " " << down << endl;
printf("%lld\n", up + down + C3[sx - 1][sy - 1] + C4[sx + 1][sy + 1]);
}
return 0;
}
Compilation message
adriatic.cpp: In function 'int main()':
adriatic.cpp:108:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
adriatic.cpp:110:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
236216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
236216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
236216 KB |
Output is correct |
| 2 |
Correct |
99 ms |
236216 KB |
Output is correct |
| 3 |
Correct |
126 ms |
236216 KB |
Output is correct |
| 4 |
Correct |
93 ms |
236216 KB |
Output is correct |
| 5 |
Correct |
99 ms |
236216 KB |
Output is correct |
| 6 |
Correct |
406 ms |
236216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
749 ms |
236216 KB |
Output is correct |
| 2 |
Correct |
126 ms |
236216 KB |
Output is correct |
| 3 |
Correct |
203 ms |
236216 KB |
Output is correct |
| 4 |
Correct |
119 ms |
236216 KB |
Output is correct |
| 5 |
Correct |
143 ms |
236216 KB |
Output is correct |
| 6 |
Correct |
1363 ms |
236216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
236216 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
