Submission #862047

#TimeUsernameProblemLanguageResultExecution timeMemory
862047sleepntsheepSnowball (JOI21_ho_t2)C++17
0 / 100
1 ms2396 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], w[N], hi[N], lo[N]; int main() { ShinLena; cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> x[i]; for (int i = 1; i <= q; ++i) cin >> w[i], w[i] += w[i-1], hi[i] = max(hi[i-1], w[i]), lo[i] = min(lo[i-1], w[i]); for (int i = 1; i <= n; ++i) { ll lft= 1e14, rgt=-1e14; { 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 (y < q) rgt = max(rgt, lo[y+1] + x[i+1]); } } 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 (y < q) lft = min(lft, hi[y+1] + x[i-1]); } } 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...