Submission #851040

#TimeUsernameProblemLanguageResultExecution timeMemory
851040math_rabbit_1028Adriatic (CEOI13_adriatic)C++14
100 / 100
192 ms163592 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int m = 2500; int n, pos[252525][2]; bool grid[2525][2525]; int up[2525][2525], dn[2525][2525], lt[2525][2525], rt[2525][2525], sum[2525][2525]; int dp[2525][2525], ans[252525]; int get(int s, int e, int l, int r) { return sum[e][r] - sum[s - 1][r] - sum[e][l - 1] + sum[s - 1][l - 1]; } int solvertdn(int x, int y) { //cout << x << y << "\n"; if (dp[x][y] >= 0) return dp[x][y]; if (get(1, x, y, m) == 0) return dp[x][y] = 0; return dp[x][y] = solvertdn( min(x, dn[x - 1][y - 1]), max(y, rt[x + 1][y + 1]) ) + get(1, x, y, m); } int solveltup(int x, int y) { //cout << x << y << "\n"; if (dp[x][y] >= 0) return dp[x][y]; if (get(x, m, 1, y) == 0) return dp[x][y] = 0; return dp[x][y] = solveltup( max(x, up[x + 1][y + 1]), min(y, lt[x - 1][y - 1]) ) + get(x, m, 1, y); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> pos[i][0] >> pos[i][1]; grid[pos[i][0]][pos[i][1]] = true; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { sum[i][j] = sum[i][j - 1] + grid[i][j]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { sum[i][j] = sum[i - 1][j] + sum[i][j]; } } for (int i = 0; i <= m + 1; i++) { for (int j = 0; j <= m + 1; j++) { up[i][j] = 0; dn[i][j] = m + 1; lt[i][j] = m + 1; rt[i][j] = 0; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { dn[i][j] = min(dn[i - 1][j], dn[i][j - 1]); if (grid[i][j]) dn[i][j] = min(dn[i][j], i); lt[i][j] = min(lt[i - 1][j], lt[i][j - 1]); if (grid[i][j]) lt[i][j] = min(lt[i][j], j); } } for (int i = m; i >= 1; i--) { for (int j = m; j >= 1; j--) { up[i][j] = max(up[i + 1][j], up[i][j + 1]); if (grid[i][j]) up[i][j] = max(up[i][j], i); rt[i][j] = max(rt[i + 1][j], rt[i][j + 1]); if (grid[i][j]) rt[i][j] = max(rt[i][j], j); } } for (int i = 0; i <= m + 1; i++) { for (int j = 0; j <= m + 1; j++) { dp[i][j] = -1; } } for (int i = 1; i <= n; i++) { solvertdn(pos[i][0], pos[i][1]); ans[i] += dp[pos[i][0]][pos[i][1]]; } for (int i = 0; i <= m + 1; i++) { for (int j = 0; j <= m + 1; j++) { dp[i][j] = -1; } } for (int i = 1; i <= n; i++) { solveltup(pos[i][0], pos[i][1]); ans[i] += dp[pos[i][0]][pos[i][1]]; } for (int i = 1; i <= n; i++) { cout << ans[i] + n - 3 << "\n"; } return 0; }
#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...