Submission #862050

#TimeUsernameProblemLanguageResultExecution timeMemory
862050sleepntsheepSnowball (JOI21_ho_t2)C++17
100 / 100
98 ms6740 KiB
#include <cstdio> #include <cstring> #include <cassert> #include <string> #include <deque> #include <vector> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <utility> using namespace std; using ll = long long; using ld = long double; #define ShinLena cin.tie(nullptr)->sync_with_stdio(false) #define N 200005 #define ALL(x) x.begin(), x.end() ll n, q, x[N], hi[N], lo[N]; int main() { ShinLena; cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> x[i]; for (ll w=0,p, i = 1; i <= q; ++i) cin >> p, w += p, hi[i] = max(hi[i-1], w), lo[i] = min(lo[i-1], w); for (int i = 1; i <= n; ++i) { ll lft= x[i], rgt=x[i]; { int l = 1, r = q; while (l <= r) { int y = (l+r)/2; if (hi[y] + x[i] > lo[y] + x[i+1]) r = y - 1, rgt = max(rgt, lo[y] + x[i+1]); else l = y + 1, rgt = max(rgt, x[i] + hi[y]); } if (i == n) rgt = x[i] + hi[q]; l = 1, r = q; while (l <= r) { int y = (l+r)/2; if (lo[y] + x[i] < hi[y] + x[i-1]) r = y - 1, lft = min(lft, hi[y] + x[i-1]); else l = y + 1, lft = min(lft, x[i] + lo[y]); } if (i == 1) lft = x[i] + lo[q]; } cout << rgt - lft << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...