oj.uz

Submission #38742

# Submission time Handle Problem Language Result Execution time Memory
38742 2018-01-06T11:33:01 Z aome Adriatic (CEOI13_adriatic) C++14
100 / 100
 346 ms 126728 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2505;
const int M = 250005;
const int INF = 1e9;

int n;
int fr[2][N], fc[2][N];
int cnt[N][N];
int ar[M], ac[M];
long long f[2][N][N];

int get(int lx, int ly, int rx, int ry) {
    return cnt[rx][ry] - cnt[lx - 1][ry] - cnt[rx][ly - 1] + cnt[lx - 1][ly - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < N; ++i) {
        fr[0][i] = fc[0][i] = INF;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> ar[i] >> ac[i];
        cnt[ar[i]][ac[i]] = 1;
        fr[0][ar[i]] = min(fr[0][ar[i]], ac[i]);
        fr[1][ar[i]] = max(fr[1][ar[i]], ac[i]);
        fc[0][ac[i]] = min(fc[0][ac[i]], ar[i]);
        fc[1][ac[i]] = max(fc[1][ac[i]], ar[i]);
    }
    int MX = 2500;
    for (int i = 1; i <= MX; ++i) {
        fr[0][i] = min(fr[0][i], fr[0][i - 1]);
        fc[0][i] = min(fc[0][i], fc[0][i - 1]);
    }
    for (int i = MX; i >= 1; --i) {
        fr[1][i] = max(fr[1][i], fr[1][i + 1]);
        fc[1][i] = max(fc[1][i], fc[1][i + 1]);
    }
    for (int i = 1; i <= MX; ++i) {
        for (int j = 1; j <= MX; ++j) {
            cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= MX; ++i) {
        for (int j = MX; j >= 1; --j) {
            int nj = max(j, fr[1][i + 1]);
            int ni = min(i, fc[0][j - 1]);
            f[0][i][j] = f[0][ni][nj] + get(1, j, i, MX);
        }
    }
    for (int i = MX; i >= 1; --i) {
        for (int j = 1; j <= MX; ++j) {
            int nj = min(j, fr[0][i - 1]);
            int ni = max(i, fc[1][j + 1]);
            f[1][i][j] = f[1][ni][nj] + get(i, 1, MX, j);
        }
    }
    for (int i = 1; i <= n; ++i) {
        long long res = f[0][ar[i]][ac[i]] + f[1][ar[i]][ac[i]] - 2;
        int tmp = get(1, 1, ar[i] - 1, ac[i] - 1) + get(ar[i] + 1, ac[i] + 1, MX, MX);
        res += tmp, res += (n - 1 - tmp);
        printf("%lld\n", res);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 126728 KB Output is correct
2 Correct 76 ms 126728 KB Output is correct
3 Correct 63 ms 126728 KB Output is correct
4 Correct 66 ms 126728 KB Output is correct
5 Correct 66 ms 126728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 126728 KB Output is correct
2 Correct 86 ms 126728 KB Output is correct
3 Correct 69 ms 126728 KB Output is correct
4 Correct 79 ms 126728 KB Output is correct
5 Correct 73 ms 126728 KB Output is correct
6 Correct 73 ms 126728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 126728 KB Output is correct
2 Correct 79 ms 126728 KB Output is correct
3 Correct 86 ms 126728 KB Output is correct
4 Correct 69 ms 126728 KB Output is correct
5 Correct 79 ms 126728 KB Output is correct
6 Correct 136 ms 126728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 126728 KB Output is correct
2 Correct 89 ms 126728 KB Output is correct
3 Correct 93 ms 126728 KB Output is correct
4 Correct 96 ms 126728 KB Output is correct
5 Correct 79 ms 126728 KB Output is correct
6 Correct 116 ms 126728 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 126728 KB Output is correct
2 Correct 346 ms 126728 KB Output is correct
3 Correct 293 ms 126728 KB Output is correct
4 Correct 299 ms 126728 KB Output is correct
5 Correct 216 ms 126728 KB Output is correct
6 Correct 296 ms 126728 KB Output is correct
7 Correct 309 ms 126728 KB Output is correct