제출 #594411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594411		keta_tsimakuridze	섬 항해 (CEOI13_adriatic)	C++14	100 / 100	362 ms	56588 KiB

adriatic

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define ll long long
const int N = 25e4 + 5, mod = 1e9 + 7, X = 2500;
int t, x[N], y[N], r[N], up[N];
int f[X + 5][X + 5];
int dp[X + 5][X + 5];
main() {
/*
7
1 7
7 5
4 5
4 8
6 6
6 1
2 3

4
1 1
2 3
3 2
4 4
*/
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<int> ans(n + 5);
    for(int t = 0; t < 2; t++) {
        for(int i = 1; i <= X; i++ ){
            for(int j = 1; j <= X; j++) f[i][j] = 0;
        }
        for(int i = 1; i <= n; i++) f[x[i]][y[i]] = 1;
        for(int i = X; i >= 1; i--) {
            r[i] = 0;
            for(int j = 1; j <= X; j++) {
                if(f[i][j]) r[i] = j;
            }
            r[i] = max(r[i], r[i + 1]);
        }
        up[0] = X + 1;
        for(int j = 1; j <= X; j++) {
            up[j] = X + 1;
            for(int i = 1; i <= X; i++) {
                if(f[i][j]) up[j] = min(up[j], i);
            }
            up[j] = min(up[j], up[j - 1]);
        }

        for(int i = 1; i <= X; i++) {
            for(int j = X; j >= 1; j--) {
                f[i][j] = f[i][j] + f[i][j + 1] + f[i - 1][j] - f[i - 1][j + 1];
                dp[i][j] = f[i][j] + dp[min(i, up[j - 1])][max(j, r[i + 1])];
            }
        }
        for(int i = 1; i <= n; i++) {
            ans[i] += dp[x[i]][y[i]] - 1;
           x[i] = X - x[i] + 1; y[i] = X - y[i] + 1;
        }

    }
    for(int i = 1; i <= n; i++) cout << ans[i] - 1 + n << "\n";
}

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

adriatic.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main() {
      | ^~~~

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