Submission #987362

#	Time	Username	Problem	Language	Result	Execution time	Memory
987362		876pol	Garden (JOI23_garden)	C++17	30 / 100	3090 ms	6796 KiB

garden

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = int;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(e, i) for (const auto &e : i)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<string, T>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

ll n, m, d;
set<ll> ss;
map<ll, ll> gaps;

inline ll nm(ll x) {
    return (x % d + d) % d;
}

inline void insert(ll x) {
    if (ss.count(x)) return;
    auto it = ss.lower_bound(x);
    ll o1 = (it == ss.begin()) ? *ss.rbegin() : *prev(it);
    ll o2 = (it == ss.end()) ? *ss.begin() : *it;
    if (--gaps[nm(o2 - o1 - 1)] == 0) {
        gaps.erase(nm(o2 - o1 - 1));
    }
    ss.insert(x);
    gaps[nm(x - o1 - 1)]++;
    gaps[nm(o2 - x - 1)]++;
};

int main() {
    cin >> n >> m >> d;
    deque<ll> xc, yc;
    deque<pll> oc;
    deque<ll> ax;
    FOR(i, 0, n) {
        ll a, b;
        cin >> a >> b;
        xc.push_back(a);
        yc.push_back(b);
        ax.push_back(a);
    }
    FOR(i, 0, m) {
        ll a, b;
        cin >> a >> b;
        oc.push_back({a, b});
        ax.push_back(a);
    }
    sort(all(xc));
    xc.erase(unique(all(xc)), xc.end());
    sort(all(yc));
    yc.erase(unique(all(yc)), yc.end());
    sort(all(oc));
    oc.erase(unique(all(oc)), oc.end());
    sort(all(ax));
    ax.erase(unique(all(ax)), ax.end());
    ll ans = INT_MAX;
    FOR(_, 0, ax.size()) {
        while (xc.front() < ax.front()) {
            xc.push_back(xc.front() + d);
            xc.pop_front();
        }
        while (oc.front().first < ax.front()) {
            oc.push_back({oc.front().first + d, oc.front().second});
            oc.pop_front();
        }
        ss.clear();
        ss.insert(yc[0]);
        gaps.clear();
        gaps[d - 1] = 1;
        FOR(i, 1, yc.size()) insert(yc[i]);
        ll mxx = xc.back();
        ll co = max(mxx, oc.back().first);
        ans = min(ans, (d - gaps.rbegin()->first) * (co - ax.front() + 1));
        for (ll i = oc.size() - 1; i >= 0; i--) {
            if (oc[i].first <= mxx) break;
            co = max(mxx, (i == 0) ? mxx : oc[i - 1].first);
            insert(oc[i].second);
            ans = min(ans, (d - gaps.rbegin()->first) * (co - ax.front() + 1));
        }

        ax.push_back(ax.front() + d);
        ax.pop_front();
    }
    cout << ans << "\n";
}

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