제출 #1127211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127211		Requiem	섬 항해 (CEOI13_adriatic)	C++20	100 / 100	265 ms	208200 KiB

adriatic

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "adriatic"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
const int D = 2500;
const int C = 12;

int n, m;
int X[MAXN], Y[MAXN];

bool exist[D + C][D + C];
int dp1[D + C][D + C], dp2[D + C][D + C], cnt[D + C][D + C];
int maxX[D + C][D + C], minX[D + C][D + C];
int maxY[D + C][D + C], minY[D + C][D + C];
int answer[MAXN], id[D + C][D + C];

int getRect(int x1, int y1, int x2, int y2){
    if (x1 > x2 or y1 > y2) return 0;
    return cnt[x2][y2] - cnt[x1 - 1][y2] - cnt[x2][y1 - 1] + cnt[x1 - 1][y1 - 1];
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n;
    FOR(i, 1, n){
        cin >> X[i] >> Y[i];
        exist[X[i]][Y[i]] = 1;
        id[X[i]][Y[i]] = i;
    }

    FOR(i, 1, D){
        FOR(j, 1, D){
            cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] + exist[i][j] - cnt[i - 1][j - 1];
        }
    }

    memset(minX, 0x3f, sizeof(minX));
    memset(minY, 0x3f, sizeof(minY));
    memset(maxX, -0x3f, sizeof(maxX));
    memset(maxY, -0x3f, sizeof(maxY));

    FOR(i, 1, D){
        FOR(j, 1, D){
            minimize(minX[i][j], minX[i - 1][j]);
            minimize(minX[i][j], minX[i][j - 1]);
            if (exist[i][j]) minimize(minX[i][j], i);

            minimize(minY[i][j], minY[i - 1][j]);
            minimize(minY[i][j], minY[i][j - 1]);
            if (exist[i][j]) minimize(minY[i][j], j);
        }
    }

    FORD(i, D, 1){
        FORD(j, D, 1){
            maximize(maxY[i][j], maxY[i + 1][j]);
            maximize(maxY[i][j], maxY[i][j + 1]);
            if (exist[i][j]) maximize(maxY[i][j], j);

            maximize(maxX[i][j], maxX[i + 1][j]);
            maximize(maxX[i][j], maxX[i][j + 1]);
            if (exist[i][j]) maximize(maxX[i][j], i);
        }
    }

    FOR(i, 1, n){
        answer[i] += n - 1;
//        answer[i] = getRect(1, 1, X[i] - 1, Y[i] - 1);
//        answer[i] += getRect(X[i] + 1, Y[i] + 1, D, D);
    }

    FOR(i, 1, D){
        FORD(j, D, 1){
            int c1 = getRect(1, j, i, D);
            if (c1 == 0) dp1[i][j] = 0;
            else{
                dp1[i][j] = c1 + dp1[min(i, minX[i - 1][j - 1])][max(j, maxY[i + 1][j + 1])];
                if (id[i][j] > 0) answer[id[i][j]] += dp1[i][j] - 1;
            }
        }
    }

    FORD(i, D, 1){
        FOR(j, 1, D){
            int c2 = getRect(i, 1, D, j);
            if (c2 == 0) dp2[i][j] = 0;
            else{
                dp2[i][j] = c2 + dp2[max(i, maxX[i + 1][j + 1])][min(j, minY[i - 1][j - 1])];
                if (id[i][j] > 0) answer[id[i][j]] += dp2[i][j] - 1;
            }
        }
    }

    FOR(i, 1, n){

        cout << answer[i] << endl;
    }


}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

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

adriatic.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main()
      | ^~~~
adriatic.cpp: In function 'int main()':
adriatic.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
adriatic.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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