Submission #1199912

#TimeUsernameProblemLanguageResultExecution timeMemory
1199912BoomydayGarden (JOI23_garden)C++20
6 / 100
3094 ms576 KiB
// // Created by adavy on 5/11/2025. // #include <bits/stdc++.h> using namespace std; using ll = long long; int N, M, D; struct Sieve{ set<int> vals; // a circular set, from 0 to D, maintain the maximum gap in the sieve set<int, greater<int>> gaps; void insert(int x){ if (vals.find(x) != vals.end()) return; if (vals.size() == 0){ vals.insert(x); return; } // get index of left and right neighbours auto right_it = vals.lower_bound(x); if (right_it == vals.end()){ right_it = vals.begin(); } int right_nei = *right_it; auto left_it = right_it; if (left_it == vals.begin()){ left_it = vals.end(); } left_it--; int left_nei = *left_it; if (left_nei != right_nei){ gaps.erase(gaps.find((right_nei - left_nei + D)%D)); } gaps.insert((x - left_nei + D)%D); gaps.insert((right_nei - x + D)%D); vals.insert(x); } int get_max_gap(){ if (gaps.size() <= 1) return D; return *gaps.begin(); } // beware of off by one error }; bool inrange(int L, int x, int R){ if (L <= R){ return (x >= L && x <= R); } else { return (x >= L || x <= R); } } int main(){ cin >> N >> M >> D; int mnans = D*D; int mnans2 = D*D; set<int> pxvals, pyvals; vector<pair<int,int>> lines; vector<vector<int>> index(D); // indexed by y value for(int i=0;i<N;++i){ int x, y; cin >> x >> y; pxvals.insert(x); pyvals.insert(y); } for (int i=0;i<M;++i){ int x, y; cin >> x >> y; index[y].push_back(x); } for(auto&a:index){ sort(a.begin(), a.end()); } // some extra code to solve naively for(int L=0;L<D;++L) for(int R=0;R<D;++R) for(int T=0;T<D;++T) for(int B = 0; B<D;++B){ bool good = 1; for (auto&x:pxvals){ if (!inrange(L, x, R)){ good = 0; } } for (auto&y:pyvals){ if (!inrange(B, y, T)){ good = 0; } } for(int y=0;y<D;++y){ for(auto&x:index[y]){ if (!(inrange(L, x, R)||inrange(B, y, T))){ good = 0; } } } if (!good) continue; mnans2 = min(mnans2, ((R-L+D)%D+1)*((T-B+D)%D+1)); } /* for(int L=0;L<D;++L){ vector<vector<int>> events(D); // representing position of R for(int Y=0;Y<D;++Y){ if (index[Y].size() == 0) continue; auto fval = lower_bound(index[Y].begin(), index[Y].end(), L); if (fval == index[Y].begin()) fval = index[Y].end(); // subtract fval--; if (fval == index[Y].end()) continue; int x = *fval; events[x].push_back(Y); } // set up and mantain the sieve Sieve sieve; // add all the normal points for (auto&y:pyvals){ sieve.insert(y); } for (int R=(L-1+D)%D;;--R, R+=D, R%=D){ // condition to break if a normal point is missed out w.r.t. x axis if (R!=(L-1+D)%D){ // if (R+1)%D is in pxvals, break if (binary_search(pxvals.begin(), pxvals.end(), (R+1)%D)){ break; } } mnans = min(mnans, ((R-L+D)%D+1)*(D+1-sieve.get_max_gap())); // add events for(auto&y:events[R] ){ sieve.insert(y); } if (R==L) break; } }*/ cout << mnans2 << endl; }
#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...