Submission #1132876

#TimeUsernameProblemLanguageResultExecution timeMemory
1132876turskaTiles (BOI24_tiles)C++20
100 / 100
142 ms17584 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; /*using ll = __int128;*/ using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const ll M = 998244353; /*const ll M = 1e9 + 7;*/ #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define ff first #define ss second #define PI 3.141592653589793238462643383279502884L const ll INFL = 1e18; const int INF = 1e9; const int maxN = 1e6+1; struct edge { int l,r; }; bool operator<(const edge &a, const edge &b) { if (a.l==b.l) return a.r < b.r; return a.l < b.l; }; set<edge> st[2]; // l<=r int cnt_odd = 0; void insert(edge e, int m) { // edges intersecting wont exists auto it = st[m].upper_bound(e); int l = e.l, r = e.r; if (it!=st[m].end()) { if (it->l==e.r) { cnt_odd -= (it->r-it->l)%2==1; r = it->r; st[m].erase(it); } } it = st[m].upper_bound(e); if (it!=st[m].begin()) { it--; if (it->r==e.l) { cnt_odd -= (it->r-it->l)%2==1; l = it->l; st[m].erase(it); } } cnt_odd += (r-l)%2==1; st[m].insert({l, r}); }; bool contains(edge e, int m) { auto it = st[m].lower_bound(e); if (it==st[m].end() || it->l>=e.r) { if (it==st[m].begin()) return false; it--; } return max(it->l, e.l)<min(it->r, e.r); } bool remove(edge e, int m) { // false if edge is in 1-m if (contains(e, 1-m)) return false; auto it = st[m].lower_bound(e); if (it==st[m].end() || it->l>=e.r) it--; cnt_odd -= (it->r-it->l)%2==1; edge f = *it; st[m].erase(it); if (f.l < e.l) { cnt_odd += (e.l-f.l)%2==1; st[m].insert({f.l, e.l}); } if (f.r > e.r) { cnt_odd += (f.r-e.r)%2==1; st[m].insert({e.r, f.r}); } return true; } void solve() { int ans = 0; map<int, vector<edge>> evt; int n, m; cin >> n >> m; vector<array<int, 2>> points(n); for (int i=0; i<n; i++) cin >> points[i][0] >> points[i][1]; points.push_back(points[0]); for (int i=0; i<n; i++) { if (points[i][1]==points[i+1][1]) continue; int l = min(points[i][1], points[i+1][1]); int r = max(points[i][1], points[i+1][1]); evt[points[i][0]].push_back({l, r}); } for (auto &[x, edges]: evt) { vector<edge> add, del; for (auto e: edges) { if (contains(e, 0)||contains(e, 1)) del.push_back(e); else add.push_back(e); } if (x%2) { if (st[0].empty()) ans = max(ans, x); if (st[1].empty()) ans = max(ans, x-1); } else { if (st[0].empty()) ans = max(ans, x-1); if (st[1].empty()) ans = max(ans, x); }; for (auto e: del) { if (!remove(e, x%2)) { cout << ans << '\n'; return; }; } for (auto e: add) { insert(e, x%2); } if (cnt_odd) break; } cout << ans << '\n'; }; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout << fixed << setprecision(12); int tc = 1; /*cin >> tc;*/ while (tc--) solve(); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...