Submission #810494

#	Time	Username	Problem	Language	Result	Execution time	Memory
810494		SorahISA	Garden (JOI23_garden)	C++17	30 / 100	3091 ms	16576 KiB

garden

#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

// bool debug_flag = false;

void solve() {
    int N, M, D; cin >> N >> M >> D;
    
    vector<pii> A(N), B(M);
    for (auto &[x, y] : A) cin >> x >> y;
    for (auto &[x, y] : B) cin >> x >> y;
    
    /// store A as row and col ///
    
    vector<int> row_A;
    vector<bool> col_A(D, 0);
    for (const pii &a : A) row_A.eb(a.X), row_A.eb(a.X + D), col_A[a.Y] = 1;
    sort(ALL(row_A)), row_A.erase(unique(ALL(row_A)), end(row_A));
    
    /// store B as vectors for each row ///
    
    vector<vector<int>> col_B(D);
    for (const pii &b : B) col_B[b.Y].eb(b.X), col_B[b.Y].eb(b.X + D);
    for (int y = 0; y < D; ++y) sort(ALL(col_B[y])), col_B[y].erase(unique(ALL(col_B[y])), end(col_B[y]));
    
    /// enumerate x0 ///
    
    int ans = D * D;
    for (int x0 = 0; x0 < D; ++x0) {
        // debug_flag = (x0 == 81);
        
        /// precalculate when to remove column from set ///
        
        vector<pii> rem_col(D);
        for (int y = 0; y < D; ++y) {
            rem_col[y] = {x0 + D, y};
            if (col_A[y]) continue;
            if (col_B[y].empty()) rem_col[y].first = -1;
            else                  rem_col[y].first = *prev(lower_bound(ALL(col_B[y]), x0 + D));
        }
        sort(RALL(rem_col));
        
        // if (debug_flag) {
        //     for (auto [pt, time] : rem_col) {
        //         cerr << pt << " " << time << "\n";
        //     }
        // }
        
        /// initailize the set ///
        
        set<int> alive_col{-1, 2*D};
        for (int i = 0; i < 2*D; ++i) alive_col.ee(i);
        
        int tmp_col = D;
        auto remove = [&](int rem) {
            // if (debug_flag) debug(rem);
            auto it = alive_col.erase(alive_col.find(rem));
            chmin(tmp_col, D - (*it - *prev(it)) + 1);
        };
        
        while (SZ(rem_col) and rem_col.back().first == -1) {
            int rem = rem_col.back().second; rem_col.pb();
            remove(rem), remove(rem + D);
        }
        
        /// enumerate x1 ///
        
        int x1 = *prev(lower_bound(ALL(row_A), x0 + D));
        for (; x1 < x0 + D; ++x1) {
            // debug_flag = (x0 == 81 and x1 == 120);
            while (SZ(rem_col) and rem_col.back().first <= x1) {
                int rem = rem_col.back().second; rem_col.pb();
                remove(rem), remove(rem + D);
            }
            chmin(ans, (x1 - x0 + 1) * tmp_col);
            // if (debug_flag) {
            //     debug(x0, x1, tmp_col);
            //     cerr << "\u001b[34m";
            //     for (int x : alive_col) cerr << x << " ";
            //     cerr << "\u001b[0m\n";
            // }
        }
    }
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

#endif

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