Submission #37204

#TimeUsernameProblemLanguageResultExecution timeMemory
37204DoanPhuDucAdriatic (CEOI13_adriatic)C++98
0 / 100
476 ms228532 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...