Submission #1176475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176475		1bin	Adriatic (CEOI13_adriatic)	C++20	100 / 100	219 ms	176240 KiB

adriatic

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int MX = 2500;
const int NMAX = 3e5;
int n, y, x;
int cnt[MX + 5][MX + 5], mnx[MX + 5][MX + 5], mny[MX + 5][MX + 5], mxx[MX + 5][MX + 5], mxy[MX + 5][MX + 5];
int dr[MX + 5][MX + 5], ul[MX + 5][MX + 5];
vector<pair<int, int>> v;

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    memset(mnx, 0x3f, sizeof(mnx));
    memset(mny, 0x3f, sizeof(mny));
    memset(mxx, -1, sizeof(mxx));
    memset(mxy, -1, sizeof(mxy));
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> y >> x;
        cnt[y][x] = 1;
        mnx[y][x] = x; mxx[y][x] = x;
        mny[y][x] = y; mxy[y][x] = y;
        v.emplace_back(y, x);
    }

    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];
            mnx[i][j] = min({mnx[i - 1][j], mnx[i][j - 1], mnx[i][j]});
            mny[i][j] = min({mny[i - 1][j], mny[i][j - 1], mny[i][j]});
        }
    for (int i = MX; i; i--)
        for (int j = MX; j; j--) {
            mxx[i][j] = max({mxx[i + 1][j], mxx[i][j + 1], mxx[i][j]});
            mxy[i][j] = max({mxy[i + 1][j], mxy[i][j + 1], mxy[i][j]});
        }

    for (int y = 1; y <= MX; y++)
        for (int x = MX; x; x--)
            dr[y][x] = cnt[y][MX] - cnt[y][x - 1] + dr[min(mny[y][x - 1], y)][max(mxx[y + 1][x], x)];

    for (int y = MX; y; y--)
        for (int x = 1; x <= MX; x++)
            ul[y][x] = cnt[MX][x] - cnt[y - 1][x] + ul[max(mxy[y][x + 1], y)][min(mnx[y - 1][x], x)];

    for (auto&[y, x] : v) {
        // cout << y << ' ' << x << ' ' << ul[y][x] << ' ' << dr[y][x] << endl;
        cout << n + ul[y][x] + dr[y][x] - 3 << '\n';
    }
    return 0;
}

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