Submission #965272

#	Time	Username	Problem	Language	Result	Execution time	Memory
965272		Pring	Garden (JOI23_garden)	C++17	15 / 100	2948 ms	181072 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 500005;
int n, m, d, p[MXN], q[MXN], r[MXN], s[MXN];

struct CPU {
    int n;
    multiset<int> MV;
    multiset<pii> MS;
    vector<int> va, vr;
    vector<pii> vm;

    void init(int _n, int id, int val) {
        n = _n;
        MV.clear();
        MS.clear();
        va.clear();
        vr.clear();
        vm.clear();
        MV.insert(n);
        va.push_back(n);
        MS.insert(mp(val, id));
        MS.insert(mp(val + n, id));
        vm.push_back(mp(val, id));
        vm.push_back(mp(val + n, id));
    }

    void PUSH(int id, int val) {
        auto R = MS.upper_bound(mp(val, id)), L = prev(MS.upper_bound(mp(val + n, id)));
        int l = (L -> fs) % n, r = (R -> fs) % n;
        // if (L -> sc == R -> sc) {
        //     MV.erase(MV.find(n));
        //     vr.push_back(n);
        // } else {
        // }
        if (MV.find(n) != MV.end()) {
            if (val != (L -> fs) % n) {
                MV.erase(MV.find(n));
                vr.push_back(n);
                MV.insert((r - val + n) % n);
                va.push_back((r - val + n) % n);
                MV.insert((val - l + n) % n);
                va.push_back((val - l + n) % n);
            }
        } else {
            MV.erase(MV.find((r - l + n) % n));
            vr.push_back((r - l + n) % n);
            MV.insert((r - val + n) % n);
            va.push_back((r - val + n) % n);
            MV.insert((val - l + n) % n);
            va.push_back((val - l + n) % n);
        }
        MS.insert(mp(val, id));
        MS.insert(mp(val + n, id));
        vm.push_back(mp(val, id));
        vm.push_back(mp(val + n, id));
    }

    void SET() {
        vm.clear();
        vr.clear();
        va.clear();
    }

    void BACK() {
        for (auto &i : vm) MS.erase(MS.find(i));
        for (auto &i : vr) MV.insert(i);
        for (auto &i : va) MV.erase(MV.find(i));
        vm.clear();
        vr.clear();
        va.clear();
    }

    int query() {
        return n + 1 - *MV.rbegin();
    }
} H, V;

void miku() {
    cin >> n >> m >> d;
    assert(m <= 8);
    FOR(i, 0, n) cin >> p[i] >> q[i];
    FOR(i, 0, m) cin >> r[i] >> s[i];
    H.init(d, 0, p[0]);
    V.init(d, 0, q[0]);
    FOR(i, 1, n) {
        debug(i);
        H.PUSH(i, p[i]);
        V.PUSH(i, q[i]);
    }
    H.SET();
    V.SET();
    int ans = INT_MAX;
    FOR(I, 0, (1 << m)) {
        FOR(i, 0, m) {
            if (I & (1 << i)) {
                H.PUSH(i + n, r[i]);
            } else {
                V.PUSH(i + n, s[i]);
            }
        }
        ans = min(ans, H.query() * V.query());
        H.BACK();
        V.BACK();
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

garden.cpp: In function 'void miku()':
garden.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
garden.cpp:107:9: note: in expansion of macro 'debug'
  107 |         debug(i);
      |         ^~~~~

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