This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |