Submission #1207987

#TimeUsernameProblemLanguageResultExecution timeMemory
1207987mychecksedadCultivation (JOI17_cultivation)C++20
65 / 100
2092 ms1332 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; ll n, m, w; array<ll, 2> a[N]; ll ans = 1e18; ll f(ll u, ll d){ vector<array<ll, 3>> A, B; vector<ll> X; for(int i = 1; i <= w; ++i){ A.pb({a[i][0] - u, a[i][0] + d, a[i][1]}); B.pb({a[i][0] + d, a[i][0] - u, a[i][1]}); X.pb(a[i][0] - u); X.pb(a[i][0] + d + 1); // cerr << A.back()[0] << ' ' << A.back()[1] << ' '<< A.back()[2] << '\n'; } X.pb(1); X.pb(n); sort(all(A)); sort(all(B)); sort(all(X)); X.erase(unique(all(X)), X.end()); int ptr = 0, ptr2 = 0; ll L = 0, R = 0, D = 0; multiset<ll> Y; // active columns for(ll x_pos: X){ if(x_pos < 1 || x_pos > n) continue; // cerr << l << ' ' << r << ' ' << col << '\n'; while(ptr < B.size() && B[ptr][0] < x_pos){ Y.erase(Y.find(B[ptr][2])); ++ptr; } while(ptr2 < A.size() && A[ptr2][0] <= x_pos){ Y.insert(A[ptr2][2]); ++ptr2; } if(Y.empty()){ return 1e18; } L = max(L, (*Y.begin()) - 1); R = max(R, m - (*prev(Y.end()))); ll last_val = (*Y.begin()); for(auto val: Y){ D = max(D, val - last_val - 1); last_val = val; } } // cerr << L << ' ' << R << ' ' << D << ' ' << d << ' ' << u << ' ' << L + R + max(0, D - L - R) + d + u << '\n'; return L + R + max(0ll, D - L - R) + u; } void solve(){ cin >> n >> m >> w; ll mn = n, mx = 1; for(int i = 1; i <= w; ++i){ cin >> a[i][0] >> a[i][1]; mn = min(mn, a[i][0]); mx = max(mx, a[i][0]); } for(int j = 1; j <= w; ++j){ ll u = (a[j][0] - 1); vector<array<ll, 2>> ST; for(int i = 1; i <= w; ++i){ ST.pb({max(1ll, a[i][0] - u), a[i][0]}); } vector<ll> D; for(int x = 0; x < ST.size(); ++x){ auto [l, r] = ST[x]; D.pb(n - r); for(int y = x + 1; y < ST.size(); ++y){ auto [l2, r2] = ST[y]; if(r < l2 || r2 < l){ if(r < l2){ D.pb(l2 - r - 1); }else{ D.pb(l - r2 - 1); } } } } sort(all(D)); D.erase(unique(all(D)), D.end()); if(D.empty()) continue; if(D.size() == 1){ ans = min(ans, f(u, D[0]) + D[0]); continue; } // for(ll d: D){ // cerr << d << ' '; // cerr << f(u, d) << '\n'; // } // cerr << '\n'; int last = 0; ll last_val = f(u, D[0]); ans = min(ans, last_val + D[0]); for(; last + 1 < D.size(); ){ int l = last + 1, r = int(D.size()) - 1, res = last + 1; ll changed_val = -1; while(l <= r){ int mid = l+r>>1; ll cur = f(u, D[mid]); if(cur != last_val){ r = mid - 1; res = mid; changed_val = cur; }else{ l = mid + 1; } } if(changed_val == -1) break; last_val = changed_val; ans = min(ans, last_val + D[res]); last = res; } } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; 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...