#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;
const int N = 3e5 + 10;
const int LG = 20;
const int A = 2500 + 10;
const int INF = 0x3f3f3f3f;
const int MAX_LEVEL = 2500;
struct Point {
int x, y;
Point () {}
Point (int x, int y) : x(x), y(y) {}
} P[N];
II f[A + 10][A + 10], g[A + 10][A + 10];
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][A][LG + 3];
void Build() {
FOR(i, 0, 1)
FOR(j, 1, A) 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];
FOR(i, 1, A)
FOR(j, 1, A) f[i][j] = g[i][j] = II(-1, -1);
}
II ComputeUp(int x, int y, int ly, int rx) {
if (f[x][y] != II(-1, -1)) return f[x][y];
if (C1[x][y] == 0) return f[x][y] = II(0, 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 f[x][y] = II(0, 0);
int s = (C1[x][y] - C1[minX][maxY] - (sx == x && sy == y));
II nxt = ComputeUp(minX, maxY, y, x);
nxt.first = nxt.first + s + nxt.second;
nxt.second += s;
return f[x][y] = nxt;
}
II ComputeDown(int x, int y, int lx, int ry) {
// if (f[level][x].count(y)) return f[level][x][y];
if (g[x][y] != II(-1, -1)) return g[x][y];
if (C2[x][y] == 0) return g[x][y] = II(0, 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 g[x][y] = II(0, 0);
int s = (C2[x][y] - C2[maxX][minY] - (sx == x && sy == y));
II nxt = ComputeDown(maxX, minY, x, y);
nxt.first = nxt.first + s + nxt.second;
nxt.second += s;
return g[x][y] = nxt;
}
void Write(int n) {
if (n == 0) {
putchar('0');
putchar('\n');
return;
}
char c[30]; int k = 0;
while (n) {
c[++k] = n % 10 + '0';
n /= 10;
}
FOD(i, k, 1) putchar(c[i]); putchar('\n');
}
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;
II up = ComputeUp(sx, sy, 1, A);
II down = ComputeDown(sx, sy, 1, A);
//cout << up << " " << down << endl;
int ans = up.first + up.second +
down.first + down.second + C3[sx - 1][sy - 1] + C4[sx + 1][sy + 1];
Write(ans);
}
return 0;
}
Compilation message
adriatic.cpp: In function 'int main()':
adriatic.cpp:130:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
adriatic.cpp:132: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);
^
adriatic.cpp: In function 'void Init()':
adriatic.cpp:39:62: warning: iteration 2509u invokes undefined behavior [-Waggressive-loop-optimizations]
FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
^
adriatic.cpp:3:40: note: containing loop
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
^
adriatic.cpp:39:13: note: in expansion of macro 'FOR'
FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
^
adriatic.cpp:39:62: warning: iteration 2509u invokes undefined behavior [-Waggressive-loop-optimizations]
FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
^
adriatic.cpp:3:40: note: containing loop
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
^
adriatic.cpp:39:13: note: in expansion of macro 'FOR'
FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
228532 KB |
Output is correct |
| 2 |
Correct |
199 ms |
228532 KB |
Output is correct |
| 3 |
Correct |
183 ms |
228532 KB |
Output is correct |
| 4 |
Incorrect |
206 ms |
228532 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
228532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
228532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
228532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
476 ms |
228532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
