Submission #934232

#TimeUsernameProblemLanguageResultExecution timeMemory
934232RegulusSnowball (JOI21_ho_t2)C++17
0 / 100
2 ms2652 KiB
#include <bits/stdc++.h> #define IO ios::sync_with_stdio(false);cin.tie(0); #define debug(x) cerr << #x << " = " << (x) << ' ' #define bug(x) cerr << (x) << ' ' #define endl cerr << '\n' #define all(v) (v).begin(), (v).end() #define SZ(v) (ll)(v).size() #define lowbit(x) (x)&-(x) #define pb emplace_back #define F first #define S second using namespace std; using ll = long long; using pll = pair<ll, ll>; //#define TEST const int N = 2e5+5; const ll LLINF = 2e18; ll a[N], ans[N]; vector<pll> vL, vR; int main(void) { IO ll n, i, Q, cur = 0, L = 0, R = 0; cin >> n >> Q; for (i=1; i <= n; ++i) cin >> a[i]; for (i=1; i <= Q; ++i) { ll x; cin >> x, cur += x; if (cur < L) L = cur, vL.pb(L, R); if (cur > R) R = cur, vR.pb(L, R); //debug(L), debug(R), endl; } //for (auto p : vL) debug(p.F), debug(p.S), endl; endl; //for (auto p : vR) debug(p.F), debug(p.S), endl; a[0] = -LLINF, a[n+1] = LLINF; for (i=1; i <= n; ++i) { int lb = 0, ub = SZ(vL)-1, mid; while (lb < ub) { mid = (lb + ub) >> 1; auto p = vL[mid]; if (a[i-1]+p.S >= a[i]+p.F) ub = mid; else lb = mid + 1; } auto p = vL[lb];// debug(lb); ll tmp = -p.F - max(a[i-1]+p.S - (a[i]+p.F), 0LL); if (lb > 0) { p = vL[lb - 1]; tmp = max(tmp, -p.F - max(a[i-1]+p.S - (a[i]+p.F), 0LL)); } ans[i] += tmp; lb = 0, ub = SZ(vR)-1; while (lb < ub) { mid = (lb + ub) >> 1; auto p = vR[mid]; if (a[i]+p.S >= a[i+1]+p.F) ub = mid; else lb = mid + 1; } p = vR[lb]; //debug(lb), endl; tmp = p.S - max(a[i]+p.S - (a[i+1]+p.F), 0LL); if (lb > 0) { p = vR[lb - 1]; tmp = max(tmp, p.S - max(a[i]+p.S - (a[i+1]+p.F), 0LL)); } ans[i] += tmp; cout << ans[i] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...