# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
812724 | piOOE | Garden (JOI23_garden) | C++17 | 469 ms | 8272 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Cycle {
vector<bool> a;
vector<int> nxt, prv;
int n = 0, mx = 0, cnt = 0;
Cycle(int n) : n(n), mx(0), cnt(0), a(n, 0), nxt(n), prv(n) {}
void ins(int i) {
a[i] = true;
int l = i == 0 ? n - 1 : i - 1, r = i + 1 == n ? 0 : i + 1;
prv[i] = a[l] ? prv[l] : i, nxt[i] = a[r] ? nxt[r] : i;
nxt[prv[i]] = nxt[i], prv[nxt[i]] = prv[i];
mx = max(mx, (nxt[i] - prv[i] + n) % n + 1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, d;
cin >> n >> m >> d;
vector<int> needx(2 * d), needy(2 * d);
vector<vector<int>> points(2 * d);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
needx[a] = needy[b] = true;
}
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
if (needx[a] || needy[b]) {
continue;
}
points[a].push_back(b);
}
for (int i = 0; i < d; ++i) {
needx[i + d] = needx[i];
needy[i + d] = needy[i];
points[i + d] = points[i];
}
int ans = d * d;
vector<vector<int>> lastVec(2 * d);
for (int L = 1; L <= d; ++L) {
if (!needx[L - 1]) {
continue;
}
int R = L;
while (!needx[R]) {
R += 1;
}
vector<int> last(d, -1);
for (int l = R - 1; l >= L; --l) {
for (int y : points[l]) {
last[y] = l;
}
for (int i = l; i < R; ++i) {
lastVec[i].clear();
}
Cycle c(d);
for (int y = 0; y < d; ++y) {
if (needy[y]) {
continue;
}
if (last[y] == -1) {
c.ins(y);
} else {
lastVec[last[y]].push_back(y);
}
}
for (int r = R; r >= l; --r) {
if (r < R) {
for (int y : lastVec[r]) {
c.ins(y);
}
}
ans = min(ans, (d - (r - l)) * (d - c.mx));
}
}
}
cout << ans << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |