Submission #864030

#TimeUsernameProblemLanguageResultExecution timeMemory
864030Danilo21Garden (JOI23_garden)C++17
75 / 100
3022 ms37320 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define pb push_back #define fi first #define se second #define en '\n' #define sp ' ' #define tb '\t' #define ri(n) int n; cin >> n #define rl(n) ll n; cin >> n #define rs(s) string s; cin >> s #define rc(c) char c; cin >> c #define rv(v) for (auto &x : v) cin >> x #define pven(v) for (auto x : v) cout << x << en #define pv(v) for (auto x : v) cout << x << sp; cout << en #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define yes cout << "YES" << en #define no cout << "NO" << en #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) #define ssort(a, b) if (a < b) swap(a, b) #define bitcnt(a) (__builtin_popcountll(a)) #define bithigh(a) (63-__builtin_clzll(a)) #define lg bithigh #define highpow(a) (1LL << (ll)lg(a)) using namespace std; struct T{ int n, mx; vector<int> on, L, R; void Insert(int i){ on[i] = 1; int prev = (i ? i-1 : n-1); int next = (i < n-1 ? i+1 : 0); int l = (on[prev] ? L[prev] : i); int r = (on[next] ? R[next] : i); if (n == 1 || l == next){ mx = n; return; } smax(mx, (r-l + n) % n + 1); R[l] = r; L[r] = l; } int Get() const { return mx; } T(int s){ n = s; mx = 0; on.assign(n, 0); L.resize(n); R.resize(n); } }; const ll LINF = 4e18; const int mxN = 1e6+10, INF = 2e9; int n, m, d, a[mxN], b[mxN], init[mxN]; set<array<int, 2> > s[2]; void Solve(){ cin >> n >> m >> d; for (int i = 0; i < n; i++){ cin >> a[i] >> b[i]; s[0].insert({b[i], i}); init[a[i]]++; } for (int i = n; i < n+m; i++){ cin >> a[i] >> b[i]; s[1].insert({b[i], i}); init[a[i]]++; } int ans = d*d; for (int i = 0; i < d; i++){ vector<int> cnt(d); for (int j = 0; j < d; j++) cnt[j] = init[j]; vector<vector<int> > J(2*d); auto x = *s[0].rbegin(); for (auto [j, k] : s[1]){ if (j > x[0]) J[j].pb(k); else cnt[a[k]]--; } T pool(d); for (int j = 0; j < d; j++) if (!cnt[j]) pool.Insert(j); smin(ans, (x[0]-i+1) * (d - pool.Get())); for (int j = x[0]+1; j < i+d; j++){ if (J[j].empty()) continue; for (int k : J[j]){ cnt[a[k]]--; if (!cnt[a[k]]) pool.Insert(a[k]); } smin(ans, (j-i+1) * (d - pool.Get())); } while ((*s[0].begin())[0] == i){ int j = (*s[0].begin())[1]; s[0].erase(s[0].begin()); s[0].insert({i+d, j}); } while ((*s[1].begin())[0] == i){ int j = (*s[1].begin())[1]; s[1].erase(s[1].begin()); s[1].insert({i+d, j}); } } cout << ans << en; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0); cout << setprecision(12) << fixed; cerr << setprecision(12) << fixed; cerr << "Started!" << endl; 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...