oj.uz

Submission #851040

# Submission time Handle Problem Language Result Execution time Memory
851040 2023-09-18T10:12:50 Z math_rabbit_1028 Adriatic (CEOI13_adriatic) C++14
100 / 100
 192 ms 163592 KB 
#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;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 158032 KB Output is correct
2 Correct 81 ms 158028 KB Output is correct
3 Correct 81 ms 158100 KB Output is correct
4 Correct 81 ms 153928 KB Output is correct
5 Correct 82 ms 158100 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 158032 KB Output is correct
2 Correct 82 ms 158040 KB Output is correct
3 Correct 82 ms 158032 KB Output is correct
4 Correct 85 ms 154248 KB Output is correct
5 Correct 85 ms 158032 KB Output is correct
6 Correct 82 ms 158044 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 158288 KB Output is correct
2 Correct 83 ms 158136 KB Output is correct
3 Correct 85 ms 158292 KB Output is correct
4 Correct 83 ms 154192 KB Output is correct
5 Correct 82 ms 158124 KB Output is correct
6 Correct 83 ms 158288 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 158760 KB Output is correct
2 Correct 89 ms 158544 KB Output is correct
3 Correct 93 ms 158544 KB Output is correct
4 Correct 88 ms 154448 KB Output is correct
5 Correct 91 ms 158524 KB Output is correct
6 Correct 88 ms 158800 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 163592 KB Output is correct
2 Correct 164 ms 162900 KB Output is correct
3 Correct 192 ms 162888 KB Output is correct
4 Correct 145 ms 160588 KB Output is correct
5 Correct 135 ms 163260 KB Output is correct
6 Correct 139 ms 163408 KB Output is correct
7 Correct 136 ms 163436 KB Output is correct