Submission #386821

#TimeUsernameProblemLanguageResultExecution timeMemory
386821nikatamlianiSnowball (JOI21_ho_t2)C++14
0 / 100
2 ms492 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5+10; ll n, m, x[N], maxp[N], minp[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; ++i) { cin >> x[i]; } ll p = 0; for(int i = 1; i <= m; ++i) { ll offset; cin >> offset; p += offset; maxp[i] = max(maxp[i - 1], p); minp[i] = min(minp[i - 1], p); cout << maxp[i] << ' ' << minp[i] << '\n'; } const ll oo = 1e15; x[0] = -oo; x[n+1] = oo; auto crit_point = [&](ll dist) { ll l = 0, r = m, ans = -1; while(r >= l) { ll middle = l + r >> 1; if(maxp[middle] >= dist + minp[middle]) { r = middle - 1; ans = middle; } else { l = middle+1; } } return ans; }; auto maximum = [&](ll a, ll b) { return max(a, b); }; auto minimum = [&](ll a, ll b) { return min(a, b); }; auto f = [&](ll id, ll A, ll B, function<ll(ll, ll)> fun) { id = max(id, 0LL); id = min(id, m); return fun(maxp[id] + A, minp[id] + B); }; for(int i = 1; i <= n; ++i) { ll lft = oo, rgh = -oo; for(int j = 0; j <= m; ++j) { lft = min(lft, f(j, x[i-1], x[i], maximum)); rgh = max(rgh, f(j, x[i], x[i+1], minimum)); } // ll point_lft = crit_point(x[i] - x[i-1]); // ll point_rgh = crit_point(x[i+1] - x[i]); // ll lft = oo, rgh = -oo; // for(int off = -1; off <= 1; ++off) { // lft = min(lft, f(point_lft+off, x[i] - x[i-1], maximum)); // rgh = max(rgh, f(point_rgh+off, x[i+1] - x[i], minimum)); // } // cout << lft << ' ' << rgh << '\n'; cout << rgh - lft << ' '; } }

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:26:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |    ll middle = l + r >> 1;
      |                ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:23:7: warning: variable 'crit_point' set but not used [-Wunused-but-set-variable]
   23 |  auto crit_point = [&](ll dist) {
      |       ^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...