제출 #952602

#제출 시각아이디문제언어결과실행 시간메모리
952602arbuzickGarden (JOI23_garden)C++17
0 / 100
93 ms6476 KiB
#include <bits/stdc++.h> using namespace std; void solve() { int n, m, d; cin >> n >> m >> d; vector<int> p(n), q(n); for (int i = 0; i < n; ++i) { cin >> p[i] >> q[i]; } vector<int> r(m), s(m); for (int i = 0; i < m; ++i) { cin >> r[i] >> s[i]; } int ans = d * d; vector<int> pp = p; sort(pp.begin(), pp.end()); vector<int> inds(m); iota(inds.begin(), inds.end(), 0); sort(inds.begin(), inds.end(), [&](int i, int j) { int ri = r[i] + 1, rj = r[j] + 1; return ri < rj; }); vector<int> ll_val(d, -1), rr_val(d, d); set<int> used; vector<int> cnt_val(d); for (int i = 0; i < n; ++i) { cnt_val[q[i]]++; if (cnt_val[q[i]] == 1) { auto it = used.lower_bound(q[i]); if (it != used.end()) { ll_val[*it] = q[i]; rr_val[q[i]] = *it; } if (it != used.begin()) { it--; rr_val[*it] = q[i]; ll_val[q[i]] = *it; } used.insert(q[i]); } } for (int i = 0; i < m; ++i) { cnt_val[s[i]]++; if (cnt_val[s[i]] == 1) { auto it = used.lower_bound(s[i]); if (it != used.end()) { ll_val[*it] = s[i]; rr_val[s[i]] = *it; } if (it != used.begin()) { it--; rr_val[*it] = s[i]; ll_val[s[i]] = *it; } used.insert(s[i]); } } vector<int> cnt_nw(d), inds_nw; for (int i = 0; i < m; ++i) { cnt_nw[s[inds[i]]]++; if (cnt_nw[s[inds[i]]] == cnt_val[s[inds[i]]]) { inds_nw.push_back(i); } } int pos = 0; for (int lx = 0; lx < d; ++lx) { int rx = pp[n - 1] + 1; int pos_nw = lower_bound(pp.begin(), pp.end(), lx) - pp.begin(); if (pos_nw != 0) { pos_nw--; rx = max(rx, pp[pos_nw] + d + 1); } auto ll = ll_val, rr = rr_val, cnt = cnt_val; int len_pr = 0, len_suff = 0, mx_diff = 0; for (int i = 0; i < d; ++i) { if (cnt[i] > 0) { if (ll[i] == -1) { len_pr = max(len_pr, i); } else { mx_diff = max(mx_diff, i - ll[i] - 1); } if (rr[i] == d) { len_suff = max(len_suff, d - i - 1); } } } for (auto i : inds_nw) { ans = min(ans, (rx - lx) * (d - max(len_pr + len_suff, mx_diff))); if (lx <= r[inds[i]]) { rx = max(rx, r[inds[i]] + 1); } else { rx = max(rx, r[inds[i]] + d + 1); } if (ll[s[inds[i]]] != -1) { rr[ll[s[inds[i]]]] = rr[s[inds[i]]]; if (rr[ll[s[inds[i]]]] == d) { len_suff = max(len_suff, d - ll[s[inds[i]]] - 1); } else { mx_diff = max(mx_diff, rr[ll[s[inds[i]]]] - ll[s[inds[i]]] - 1); } } if (rr[s[inds[i]]] != d) { ll[rr[s[inds[i]]]] = ll[s[inds[i]]]; if (ll[rr[s[inds[i]]]] == -1) { len_pr = max(len_pr, rr[s[inds[i]]]); } } } ans = min(ans, (rx - lx) * (d - max(len_pr + len_suff, mx_diff))); int pos2 = pos; vector<int> used2(d); while (pos2 < m && r[inds[pos2]] == lx) { used2[s[inds[pos2]]] = pos2 + 1; pos2++; } vector<int> inds_nw_vl; int val = -1; for (auto i : inds_nw) { if (used2[s[inds[i]]]) { assert(val == -1); val = used2[s[inds[i]]] - 1; } else { inds_nw_vl.push_back(i); } } if (val != -1) { inds_nw_vl.push_back(val); } pos = pos2; } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...