Submission #810339

#	Time	Username	Problem	Language	Result	Execution time	Memory
810339		model_code	Garden (JOI23_garden)	C++17	100 / 100	591 ms	8228 KiB

garden

// O(N + M + D^2)
#include<bits/stdc++.h>

using namespace std;

// N 個の要素が円環状に並んでいて，最初すべて off
// on(i) : 要素 i を on にする
// get() : on である要素が連続する部分の長さの最大値を返す
struct S {
    int n, mx;
    vector<bool> is_on;
    vector<int> l, r;
    
    S(int n) : n(n), mx(0), is_on(n), l(n), r(n) {}
    
    void on(int i) {
        is_on[i] = true;
        int pre = (i ? i - 1 : n - 1);
        int nx = (i < n - 1 ? i + 1 : 0);
        int nl = (is_on[pre] ? l[pre] : i);
        int nr = (is_on[nx] ? r[nx] : i);
        if (n == 1 or nl == nx) {
            mx = n;
            return;
        }
        mx = max(mx, (nr - nl + n) % n + 1);
        r[nl] = nr;
        l[nr] = nl;
    }
    
    int get() { return mx; }
};

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    // トーラス状になった D x D 領域の上で考える
    vector<bool> x_must(d), y_must(d); // 各 x, y 座標が必ず庭に含まれるかどうか
    for (int i = 0; i < n; i++) {
        int p, q;
        cin >> p >> q;
        x_must[p] = true;
        y_must[q] = true;
    }
    vector <vector<int>> rq(d); // rq[i] : x = i が庭に含まれない場合，含まなければならなくなる y 座標のリスト
    for (int i = 0; i < m; i++) {
        int r, s;
        cin >> r >> s;
        if (x_must[r] or y_must[s]) continue;
        rq[r].push_back(s);
    }
    for(int i = 0; i < d; i++) x_must.push_back(x_must[i]);
    for(int i = 0; i < d; i++) rq.push_back(rq[i]);
    int ans = d * d;
    vector <vector<int>> last_ls(2 * d);
    for (int L = 1; L <= d; L++) {
        if (!x_must[L - 1]) continue;
        int R = L;
        while (!x_must[R]) ++R;
        vector<int> last(d, -1);
        // 選ばない x の範囲を全探索
        for (int l = R; l >= L; l--) {
            if (l < R) {
                for (int i: rq[l]) last[i] = l;
            }
            for (int i = l; i < R; i++) last_ls[i].clear();
            for (int i = 0; i < d; i++) {
                if (last[i] != -1) last_ls[last[i]].push_back(i);
            }
            S s(d);
            for (int i = 0; i < d; i++) if (!y_must[i] and last[i] == -1) s.on(i);
            for (int r = R; r >= l; r--) {
                if (r < R) {
                    for (int i: last_ls[r]) s.on(i);
                }
                ans = min(ans, (d - (r - l)) * (d - s.get()));
            }
        }
        L = R;
    }
    cout << ans << endl;
}

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