제출 #1206249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206249		LucasLe	Garden (JOI23_garden)	C++20	75 / 100	3094 ms	3516 KiB

garden

#include <bits/stdc++.h>

template<typename T>
bool minimize(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool maximize(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int MOD = 998244353;

template<typename T>
void add(T &x, T y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

template<typename T>
T bin_pow(T x, T y) {
    T res = 1;
    while (y) {
        if (y & 1)
            res = 1ll * res * x % MOD;
        x = 1ll * x * x % MOD;
        y >>= 1;
    }
    return res;
}

int divi(int x, int y) {
    return x * bin_pow(y, MOD - 2) % MOD;
}

#define fi first
#define se second
#define pii std::pair<int, int>
#define ld long double

const int maxn = 5005;

int n, m, d;
int tmp_cnt[maxn + 5], cnt[maxn + 5];
int left[maxn + 5], right[maxn + 5];
bool point_row[maxn + 5];
bool point_col[maxn + 5];

std::vector<int> g[maxn + 5];

void solve() {
    std::cin >> n >> m >> d;
    for (int i = 1; i <= n; ++i) {
        int x, y; std::cin >> x >> y;
        point_col[x] = true;
        cnt[y]++;
    }
    for (int i = 1; i <= m; ++i) {
        int x, y; std::cin >> x >> y;
        g[x].push_back(y);
        cnt[y]++;
    }
    int cnt_reqcol = 0;
    for (int i = 0; i < d; ++i) {
        cnt_reqcol += point_col[i];
    }
    int res = d * d;
    for (int pivot = 0; pivot < d; ++pivot) {
        for (int i = 0; i < d; ++i) {
            tmp_cnt[i] = cnt[i];
        }
        int mx_dis = 0, mn_row = d, mx_row = -1;
        for (int i = 0, prv = -1; i < d; ++i) {
            if (!cnt[i]) continue;
            mn_row = std::min(mn_row, i);
            mx_row = std::max(mx_row, i);
            if (prv == -1) {
                left[i] = i;
                right[i] = i;
            } else {
                left[i] = prv;
                right[prv] = i;
                mx_dis = std::max(mx_dis, i - prv - 1);
            }
            prv = i;
        }
        left[mn_row] = mx_row;
        right[mx_row] = mn_row;
        mx_dis = std::max(mx_dis, d - (mx_row - mn_row + 1));
        int st = pivot, cnt_col = 0;
        while (true) {
            cnt_col += point_col[st];
            // delete rows
            for (int y : g[st]) {
                tmp_cnt[y]--;
                if (!tmp_cnt[y]) {
                    int lft = left[y];
                    int rgt = right[y];
                    right[lft] = rgt;
                    left[rgt] = lft;
                    mx_dis = std::max(mx_dis, (rgt - lft - 1 + d) % d);
                }
            }
            // calculate area
            if (cnt_col == cnt_reqcol) {
                int len = (st < pivot ? d - (pivot - st - 1) : st - pivot + 1);
                res = std::min(res, len * (d - mx_dis));
//                if (res == 6) {
//                    std::cout << "piv " << pivot << ' ' << st << ' ' << mx_dis << ' ' << mn_row << ' ' << mx_row << '\n';
//                }
            }
            st++;
            if (st >= d) st = 0;
            if (st == pivot)
                break;
        }
    }
    std::cout << res << '\n';
}

int main() {
    // std::freopen("input.txt", "r", stdin);
    // std::freopen("i.inp", "r", stdin);
    // std::freopen("sushi.out", "w", stdout);

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    // clock_t start = clock();

    int tc = 1;
//    std::cin >> tc;
    while (tc--)
        solve();

    // std::cerr << "Time elapsed: " << clock() - start << " ms\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 0 / 25