Submission #414454

#TimeUsernameProblemLanguageResultExecution timeMemory
414454amoo_safarCultivation (JOI17_cultivation)C++17
5 / 100
5 ms780 KiB
// vaziat meshki-ghermeze ! #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' // #define int ll using namespace std; typedef long long ll; typedef long double ld; typedef string str; typedef pair<int, int> pii; const ll Mod = 1000000007LL; const int N = 3e2 + 10; const int Inf = 2'000'000'001; const ll Log = 30; int n, R, C; pii A[N]; // 0, x, y -> C + R < x -> y // 1, x, y -> C < x -> y // 2, x, y -> R < x -> y typedef pii con; typedef pair<con, int> Query; vector<Query> Q, TQ, V0, V1; typedef pair<con, con> iff; vector< pair<iff, int> > cons; bool Better(con A, con B){ if(A.F != B.F) return false; return A.S >= B.S; } bool Better(iff A, iff B){ return Better(A.F, B.F) && Better(A.S, B.S); } bool Sat(con A, int i, int j){ if(A.F == 0) return i + j < A.S; if(A.F == 1) return i < A.S; return j < A.S; } void Check(int l, int r){ int ln = r - l - 1; vector<int> V; for(int k = 1; k <= n; k++){ if(l < A[k].F && A[k].F < r) V.pb(A[k].S); } sort(all(V)); int sz = Q.size(); vector< pair<con, int> > tmp; if(!V.empty() && V[0] > 1) tmp.pb({{1, V[0] - 1}, ln}); if(!V.empty() && V.back() < C) tmp.pb({{2, C - V.back()}, ln}); for(int i = 0; i + 1 < (int) V.size(); i++){ if(0 < V[i + 1] - V[i] - 1) tmp.pb({{0, V[i + 1] - V[i] - 1}, ln}); } if(V.empty()) tmp.pb({{1, C}, ln}); sort(all(tmp)); int cnt = 0; for(int i = 0; i < (int) tmp.size(); i++) if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1].F, tmp[i].F)) ) Q.pb(tmp[i]), cnt ++; // cerr << "!! " << ' ' << cnt << '\n'; for(int i = sz; i < (int) Q.size(); i++) TQ.pb(Q[i]); // Q.resize(sz); } int ans[N][N]; // C R pii Inter(pii A, pii B){ return pii(max(A.F, B.F), min(A.S, B.S)); } pii Inter(con c, int v){ if(c.F == 0){ if(v < c.S) return pii(0, v + 1); return pii(v + 1, 0); } else if(c.F == 1){ return pii(0, c.S); } return pii((v - c.S) + 1, v + 1); } pii Inter(iff c, int v){ return Inter(Inter(c.F, v), Inter(c.S, v)); } vector<iff> act; int max_sz = 0; void Uni(){ vector<iff> tmp = act; act.clear(); sort(all(tmp),[&](auto e1, auto e2){ if(e1.F.F != e2.F.F) return e1.F.F < e2.F.F; if(e1.S.F != e2.S.F) return e1.S.F < e2.S.F; return pii(e1.F.S, e1.S.S) < pii(e2.F.S, e2.S.S); }); for(int i = 0; i < (int) tmp.size(); i++) if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1], tmp[i])) ) act.pb(tmp[i]); max_sz = max(max_sz, (int) act.size()); } bool Valid(int v){ // return false; // vector<int> mk(v + 1, 0); // v = min(C - 1 + C - 1, v); // for(int i = 0, j = v; i < C; i++, j--) // if(0 <= j && j < C && ans[i][j] == 0) // return true; // return false; pii seg = pii(0, C); if(v < C) seg = pii(0, v + 1); else seg = pii(v - (C - 1), C); // cerr << "!! " << v << ' ' << seg.F << ' ' << seg.S << '\n'; vector<pii> Al; for(auto fi : act){ pii X = Inter(fi, v); X = Inter(X, seg); // X.S = min(X.S, v + 1); // X.F = max(X.F, 0); if(X.F >= X.S) continue; Al.pb(X); // for(int i = X.F; i < X.S; i++) mk[i] = 1; } // sort(all(Al)); int nw = seg.F; for(auto [l, r] : Al){ if(nw < l) return true; nw = max(nw, r); } if(nw != seg.S) return true; return false; // for(int i = 0; i <= v; i++){ // if(i < C && v - i < C && mk[i] == 0) // return true; // } // return false; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> R >> C >> n; for(int i = 1; i <= n; i++){ cin >> A[i].F >> A[i].S; } sort(A + 1, A + n + 1); // vector<int> V; // sort(all(V)); // for(int i = 1; i <= n; i++) V.pb(A[i].S); // int mn_S = 0; // for(int i = 0; i < n; i++) // mn_S = max(mn_S, V[i + 1] - V[i] - 1); // Check(0, R + 1); // int mx = (A[1].F - 1) + (R - A[n].F); Check(0, R + 1); for(auto &[cn, sm] : Q) sm = Inf; // debug(Q.size()); TQ.clear(); int sz = Q.size(); for(int i = 1; i <= n; i++) Check(0, A[i].F); Q.resize(sz); V0 = TQ; TQ.clear(); for(int i = 1; i <= n; i++) Check(A[i].F, R + 1); Q.resize(sz); V1 = TQ; TQ.clear(); for(auto [c1, v1] : V0) for(auto [c2, v2] : V1) cons.pb({{min(c1, c2), max(c1, c2)}, v1 + v2}); // debug(Q.size()); Q.resize(sz); // debug(Q.size()); for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) if(A[j].F - 1 > A[i].F) Check(A[i].F, A[j].F); // debug(Q.size()); for(auto [c1, v1] : Q) cons.pb({{c1, c1}, v1}); sort(all(cons), [&](auto e1, auto e2){ return e1.S > e2.S; }); // debug("X"); // debug(cons.size()); ll ANS = R + C; cons.pb({{{0, 0}, {0, 0}}, 0}); int la = 0; int bs = 0; ll L = -1; ll la_bs = -1; for(auto [fi, v] : cons){ // debug(v); // int CC = C + C; // for(int i = 0; i < C; i++){ // for(int j = 0; j < C; j++) // if(!ans[i][j]) // // CC = min(CC, i + j); // ANS = min(ANS, i + j + v); // } if(la == v){ act.pb(fi); continue; } la = v; if(v == Inf){ act.pb(fi); continue; } Uni(); bs++; ll Rb = C + C - 1; ll mid; if(Valid(L + 1)){ Rb = L + 1; } else { while(L + 1 < Rb){ mid = (L + Rb) >> 1; if(Valid(mid)) Rb = mid; else L = mid; } } if(Rb != C + C - 1) ANS = min(ANS, 0ll + Rb + v); // la = v; act.pb(fi); } // debug(ANS); // debug(max_sz); // debug(bs); cout << ANS << '\n'; return 0; }

Compilation message (stderr)

cultivation.cpp: In function 'int32_t main()':
cultivation.cpp:215:5: warning: unused variable 'la_bs' [-Wunused-variable]
  215 |  ll la_bs = -1;
      |     ^~~~~
#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...