제출 #23452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23452		Bruteforceman	섬 항해 (CEOI13_adriatic)	C++11	100 / 100	499 ms	224580 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;
int cnt[2505][2505];
long long dp[2505][2505];
long long fn[2505][2505];

pair <int, int> top[2505][2505];
pair <int, int> bot[2505][2505];
pair <int, int> point[250005];

const int maxn = 2500;
const int inf = 1e8;


int get_sum(int _top, int _bottom, int _left, int _right) {
    if(_top > _bottom) return 0;
    if(_left > _right) return 0;
    return cnt[_bottom][_right] - cnt[_top - 1][_right] - cnt[_bottom][_left - 1] + cnt[_top - 1][_left - 1];
}

void nextDp(int i, int j) {
            int p = max(i, bot[i + 1][j + 1].first);
            int q = min(j, top[i - 1][j - 1].second);
            cout << p << " " << q << endl;
}
void nextFn(int i, int j) {
            int p = max(i, bot[i + 1][j + 1].first);
            int q = min(j, top[i - 1][j - 1].second);
            cout << p << " " << q << endl;
}

int main() {

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        point[i] = make_pair(x, y);

        cnt[x][y] += 1;
    }
    for(int i = 1; i <= maxn; i++) {
        for(int j = 1; j <= maxn; j++) {
            cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
        }
    }

    for(int i = 1; i <= maxn; i++) {
        for(int j = 1; j <= maxn; j++) {
            if(get_sum(i, i, 1, j)) top[i][j].first = i;
            else top[i][j].first = inf;
            if(i > 1) top[i][j].first = min(top[i][j].first, top[i-1][j].first);

            if(get_sum(1, i, j, j)) top[i][j].second = j;
            else top[i][j].second = inf;
            if(j > 1) top[i][j].second = min(top[i][j].second, top[i][j-1].second);
        }
    }
    for(int i = maxn; i >= 1; i--) {
        for(int j = maxn; j >= 1; j--) {
            if(get_sum(i, i, j, maxn)) bot[i][j].first = i;
            else bot[i][j].first = 0;
            if(i < maxn) bot[i][j].first = max(bot[i][j].first, bot[i + 1][j].first);

            if(get_sum(i, maxn, j, j)) bot[i][j].second = j;
            else bot[i][j].second = 0;
            if(j < maxn) bot[i][j].second = max(bot[i][j].second, bot[i][j + 1].second);
        }
    }
    for(int i = 0; i <= maxn; i++) {
        top[0][i] = make_pair(inf, inf);
        top[i][0] = make_pair(inf, inf);
    }
    for(int i = 0; i <= maxn; i++) {
        bot[maxn + 1][i] = make_pair(0, 0);
        bot[i][maxn + 1] = make_pair(0, 0);
    }
    for(int i = 1; i <= maxn; i++) {
        for(int j = maxn; j >= 1; j--) {
            int p = min(i, top[i - 1][j - 1].first);
            int q = max(j, bot[i + 1][j + 1].second);
            if(p == i && q == j) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[p][q] + get_sum(1, i, j, maxn);
            }
        }
    }
    for(int i = maxn; i >= 1; i--) {
        for(int j = 1; j <= maxn; j++) {
            int p = max(i, bot[i + 1][j + 1].first);
            int q = min(j, top[i - 1][j - 1].second);

            if(p == i && q == j) {
                fn[i][j] = 0;
            } else {
                fn[i][j] = fn[p][q] + get_sum(i, maxn, 1, j);
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        int x = point[i].first;
        int y = point[i].second;
        long long ans = get_sum(1, x-1, 1, y-1) + get_sum(x+1, maxn, y+1, maxn);
        ans += max(0LL, dp[x][y] - 1);
        ans += max(0LL, fn[x][y] - 1);
        ans += get_sum(x, maxn, 1, y) - 1;
        ans += get_sum(1, x, y, maxn) - 1;

        // cout << fn[x][y] << " " << dp[x][y] << endl;
        printf("%lld\n", ans);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

adriatic.cpp: In function 'int main()':
adriatic.cpp:35:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
adriatic.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
                               ^

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20