Submission #37191

#TimeUsernameProblemLanguageResultExecution timeMemory
37191DoanPhuDucAdriatic (CEOI13_adriatic)C++98
10 / 100
2000 ms236216 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; 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 = 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; cout << up + down + C3[sx - 1][sy - 1] + C4[sx + 1][sy + 1] << endl; } return 0; }

Compilation message (stderr)

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 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...