제출 #904017

#제출 시각아이디문제언어결과실행 시간메모리
904017denniskimGarden (JOI23_garden)C++17
0 / 100
1706 ms95256 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) ll n, m, D; pll a[500010], b[500010]; vector<ll> A[5010], B[5010]; ll arr[5010][5010]; set<ll> V; int main(void) { fastio cin >> n >> m >> D; for(ll i = 1 ; i <= n ; i++) { cin >> a[i].fi >> a[i].se; V.insert(a[i].fi); } for(ll i = 1 ; i <= m ; i++) cin >> b[i].fi >> b[i].se; for(ll i = 1 ; i <= n ; i++) A[a[i].se].push_back(a[i].fi); for(ll i = 1 ; i <= m ; i++) B[b[i].se].push_back(b[i].fi); for(ll i = 0 ; i < D ; i++) { compress(A[i]); compress(B[i]); } ll ans = INF; for(ll x = 0 ; x < D ; x++) { vector< pair<pll, ll> > vec; vector<ll> vv; multiset<ll> st, gap; for(ll i = 0 ; i < D ; i++) { ll l = 0, r = (ll)A[i].size() - 1; while(l <= r) { ll mid = (l + r) >> 1; if(A[i][mid] >= x) r = mid - 1; else l = mid + 1; } if(!A[i].empty()) { if(l < (ll)A[i].size()) vec.push_back({{A[i][l], i}, 1}); else vec.push_back({{A[i][0] + D, i}, 1}); } if(B[i].empty()) continue; vv.push_back(i); l = 0, r = (ll)B[i].size() - 1; while(l <= r) { ll mid = (l + r) >> 1; if(B[i][mid] >= x) r = mid - 1; else l = mid + 1; } if(r == -1) vec.push_back({{B[i].back(), i}, 2}); else vec.push_back({{B[i][r] + D, i}, 2}); } ll siz = 0; ll last = x, now = INF; ll S = x; compress(vv); siz = (ll)vv.size(); for(ll i = 0 ; i < siz ; i++) { st.insert(vv[i]); if(i >= 1) { gap.insert(vv[i] - vv[i - 1]); now = min(now, D - vv[i] + vv[i - 1] + 1); } } sort(vec.begin(), vec.end()); siz = (ll)vec.size(); for(ll i = 0 ; i < siz ; i++) { if(vec[i].se == 1) { S = max(S, vec[i].fi.fi); auto p = st.lower_bound(vec[i].fi.se); ll L = -1, R = -1; if(p != st.end()) R = (*p); if(p != st.begin()) { p--; L = (*p); } st.insert(vec[i].fi.se); if(L != -1 || R != -1) { if(L == -1) gap.insert(R - vec[i].fi.se); else if(R == -1) gap.insert(vec[i].fi.se - L); else { gap.erase(gap.find(R - L)); gap.insert(R - vec[i].fi.se); gap.insert(vec[i].fi.se - L); } } } else { auto p = st.lower_bound(vec[i].fi.se); ll L = -1, R = -1; p++; if(p != st.end()) R = (*p); p--; if(p != st.begin()) { p--; L = (*p); } st.erase(st.find(vec[i].fi.se)); if(L != -1 || R != -1) { if(L == -1) gap.erase(gap.find(R - vec[i].fi.se)); else if(R == -1) gap.erase(gap.find(vec[i].fi.se - L)); else { gap.insert(R - L); gap.erase(gap.find(R - vec[i].fi.se)); gap.erase(gap.find(vec[i].fi.se - L)); } } } if(vec[i].fi.fi != last) arr[x][last] = now; last = vec[i].fi.fi; if(gap.empty()) now = 1; else { now = D - (*gap.rbegin()) + 1; if(!st.empty()) now = min(now, (*st.rbegin()) - (*st.begin()) + 1); } } arr[x][last] = now; for(ll i = x ; i < D * 2 ; i++) { if(arr[x][i]) continue; arr[x][i] = arr[x][i - 1]; } for(ll j = S ; j < D * 2 ; j++) { if(arr[x][j] != INF) ans = min(ans, (j - x + 1) * arr[x][j]); } } cout << ans; 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...