Submission #38742

#	Time	Username	Problem	Language	Result	Execution time	Memory
38742		aome	섬 항해 (CEOI13_adriatic)	C++14	100 / 100	346 ms	126728 KiB

adriatic

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20