Submission #469320

#TimeUsernameProblemLanguageResultExecution timeMemory
469320jason7777Snowball (JOI21_ho_t2)C++14
100 / 100
137 ms15300 KiB
#pragma GCC optmize ("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; #define spIO ios::sync_with_stdio(false);cin.tie(0) #define mem(x,va) memset(x,va,sizeof(x)) #define for0(i,n) for(int i=0;i<n;i++) #define for1(i,n) for(int i=1;i<=n;i++) typedef long long ll; typedef long double ld; const ll mod = 1e9 + 7; inline ll inv(ll x, ll MOD = mod) { ll power = MOD - 2, ret = 1; while (power) { if (power & 1) (ret *= x) %= MOD; power >>= 1; (x *= x) %= MOD; } return ret; } inline ll gcd(ll x, ll y) { if (y == 0) return x; return gcd(y, x % y); } ll pow2(ll target, ll p) { ll ret = 1; while (p) { if (p & 1) (ret *= target) %= mod; p >>= 1; (target *= target) %= mod; } return ret; } ll n, q; ll x[200000 + 5], w[200000 + 5], r[200000 + 5], l[200000 + 5], ans[200000 + 5]; ll bs(ll tar) { int left = 0, right = q + 1, mid; while (left != right) { mid = (left + right) / 2; if (r[mid] + l[mid] <= tar) left = mid + 1; else right = mid; } return left; } int main() { spIO; cin >> n >> q; for1(i, n) cin >> x[i]; for1(i, q) cin >> w[i]; ll ip = 0; l[0] = r[0] = 0; for1(i, q) { ip += w[i]; r[i] = max(r[i - 1], ip); l[i] = max(l[i - 1], -ip); } ans[1] += l[q]; for (int i = 2; i <= n; i++) { if (l[q] + r[q] <= x[i] - x[i - 1]) { ans[i - 1] += r[q]; ans[i] += l[q]; } else { ll t = bs(x[i] - x[i - 1]); if (r[t] - r[t - 1] > 0) { ans[i - 1] += x[i] - x[i - 1] - l[t]; ans[i] += l[t]; } else { ans[i] += x[i] - x[i - 1] - r[t]; ans[i - 1] += r[t]; } } //cout << i - 1 << ' ' << i << ' ' << ans[i - 1] << ' ' << ans[i] << '\n'; } ans[n] += r[q]; for1(i, n) cout << ans[i] << ' '; cout << '\n'; } /* */

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    1 | #pragma GCC optmize ("O3,unroll-loops")
      | 
Main.cpp: In function 'int main()':
Main.cpp:7:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    7 | #define for1(i,n) for(int i=1;i<=n;i++)
      |                   ^~~
Main.cpp:98:2: note: in expansion of macro 'for1'
   98 |  for1(i, n) cout << ans[i] << ' '; cout << '\n';
      |  ^~~~
Main.cpp:98:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |  for1(i, n) cout << ans[i] << ' '; cout << '\n';
      |                                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...