Submission #987417

#	Time	Username	Problem	Language	Result	Execution time	Memory
987417		876pol	Garden (JOI23_garden)	C++17	100 / 100	1562 ms	14780 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 << ")";
}

int main() {
    ll n, m, d;
    cin >> n >> m >> d;
    vec<ll> yc;
    deque<ll> xc;
    deque<ll> ax;
    vec<bool> rx(d), ry(d);
    FOR(i, 0, n) {
        ll a, b;
        cin >> a >> b;
        xc.push_back(a);
        yc.push_back(b);
        ax.push_back(a);
        rx[a] = ry[b] = 1;
    }
    vec<deque<ll>> loc(d);
    FOR(i, 0, m) {
        ll a, b;
        cin >> a >> b;
        if (!rx[a] && !ry[b]) {
            ax.push_back(a);
            loc[b].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(ax));
    ax.erase(unique(all(ax)), ax.end());
    FOR(i, 0, d) {
        sort(all(loc[i]));
        loc[i].erase(unique(all(loc[i])), loc[i].end());
    }
    auto nm = [&](ll x) { return (x % d + d) % d; };
    ll ans = INT_MAX;
    vec<vec<ll>> objs(d);
    vec<ll> nn1;
    nn1.reserve(d);
    vec<pll> oc;
    oc.reserve(d);
    vec<list<ll>::iterator> its(d);
    FOR(_, 0, ax.size()) {
        FOR(i, 0, d) objs[i].clear();
        nn1.clear();
        oc.clear();
        while (xc.front() < ax.front()) {
            xc.push_back(xc.front() + d);
            xc.pop_front();
        }
        ll mxx = xc.back();

        FOR(i, 0, d) {
            if (loc[i].empty()) continue;
            while (loc[i].front() < ax.front()) {
                loc[i].push_back(loc[i].front() + d);
                loc[i].pop_front();
            }
            if (mxx <= loc[i].back()) {
                objs[loc[i].back() - ax.front()].push_back(i);
                nn1.push_back(i);
            }
        }
        FOR(i, 0, objs.size())
        TRAV(e, objs[i]) oc.push_back({i + ax.front(), e});
        list<ll> l;
        ll i1 = 0, i2 = 0;
        while (i1 < yc.size() && i2 < nn1.size()) {
            if (yc[i1] < nn1[i2]) {
                l.push_back(yc[i1++]);
            } else {
                l.push_back(nn1[i2++]);
            }
        }
        while (i1 < yc.size()) {
            l.push_back(yc[i1++]);
        }
        while (i2 < nn1.size()) {
            l.push_back(nn1[i2++]);
        }
        ll mxgap = nm(*l.begin() - *l.rbegin() - 1);
        for (auto it = l.begin(); it != l.end(); it++) {
            its[*it] = it;
            if (it != prev(l.end())) {
                mxgap = max(mxgap, *next(it) - *it - 1);
            }
        }
        ll co = mxx;
        ans = min(ans, (d - mxgap) * (co - ax.front() + 1));
        TRAV(e, oc) {
            co = e.first;
            auto it = next(its[e.second]);
            l.erase(its[e.second]);
            if (it == l.begin() || it == l.end()) {
                mxgap = max(mxgap, nm(*l.begin() - *l.rbegin() - 1));
            } else {
                mxgap = max(mxgap, *it - *prev(it) - 1);
            }
            ans = min(ans, (d - mxgap) * (co - ax.front() + 1));
        }
        ax.push_back(ax.front() + d);
        ax.pop_front();
    }
    cout << ans << "\n";
}

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:104:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while (i1 < yc.size() && i2 < nn1.size()) {
      |                ~~~^~~~~~~~~~~
garden.cpp:104:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while (i1 < yc.size() && i2 < nn1.size()) {
      |                                  ~~~^~~~~~~~~~~~
garden.cpp:111:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while (i1 < yc.size()) {
      |                ~~~^~~~~~~~~~~
garden.cpp:114:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (i2 < nn1.size()) {
      |                ~~~^~~~~~~~~~~~

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