Submission #1097681

#TimeUsernameProblemLanguageResultExecution timeMemory
1097681Alihan_8Snowball (JOI21_ho_t2)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array using i64 = long long; const i64 inf = 1e18; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector <i64> X(n + 2); for ( int i = 1; i <= n; i++ ){ cin >> X[i]; } X[0] = -inf, X[n + 1] = inf; vector <i64> Q(q); for ( auto &x: Q ) cin >> x; vector <ar<i64,2>> f(q); i64 cnt = 0; for ( int i = 0; i < q; i++ ){ if ( i > 0 ) f[i] = f[i - 1]; cnt += Q[i]; f[i][0] = min(f[i][0], cnt); f[i][1] = max(f[i][1], cnt); } sort(all(f), [&](auto &u, auto &v){ return u[1] - u[0] < v[1] - v[0]; }); vector <i64> A(n + 1), B(n + 1); for ( int i = 1; i <= n; i++ ){ A[i] = X[i] - X[i - 1]; B[i] = X[i + 1] - X[i]; } vector <i64> L(n + 1), R(n + 1); { // L vector <int> p(n); iota(all(p), 1); sort(all(p), [&](int &u, int &v){ return A[u] < A[v]; }); vector <i64> pf(q + 1, inf), sf(q + 2, inf); for ( int i = 0; i < q; i++ ) pf[i + 1] = min(pf[i], f[i][0]); for ( int i = q; i > 0; i-- ) sf[i] = min(sf[i + 1], f[i - 1][1]); int j = 0; for ( auto &i: p ){ L[i] = A[i]; for ( int j = 0; j < q; j++ ){ L[i] = min(L[i], max(f[j][1], f[j][0] + A[i])); } while ( j < q && f[j][1] <= A[i] + f[j][0] ) j++; for ( int k = 0; k < q; k++ ){ if ( k < j ) L[i] = min(L[i], f[j][0] + A[i]); else L[i] = min(L[i], f[j][1]); } //~ L[i] = min({L[i], pf[j] + A[i], sf[j + 1]}); } } { // R vector <int> p(n); iota(all(p), 1); sort(all(p), [&](int &u, int &v){ return B[u] < B[v]; }); vector <i64> pf(q + 1, -inf), sf(q + 2, -inf); for ( int i = 0; i < q; i++ ) pf[i + 1] = max(pf[i], f[i][1]); for ( int i = q; i > 0; i-- ) sf[i] = max(sf[i + 1], f[i - 1][0]); int j = 0; for ( auto &i: p ){ for ( int j = 0; j < q; j++ ){ R[i] = max(R[i], min(f[j][0] + B[i], f[j][1])); } continue; while ( j < q && f[j][1] <= B[i] + f[j][0] ) j++; R[i] = max({R[i], pf[j], sf[j + 1] + B[i]}); } } for ( int i = 1; i <= n; i++ ){ cout << R[i] - L[i] + A[i] << endl; } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...