//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
using ost = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define trav(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define pb push_back
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int N, Q;
cin >> N >> Q;
vl pos(N);
F0R(i, N) cin >> pos[i];
vl shf(Q);
F0R(i, Q) cin >>shf[i];
vl ans(N, 0);
vl lb(Q+1, 0), ub(Q+1, 0);
vi trn(Q+1, 0);
vl cvrg(Q+1, 0);
ll cur = 0;
F0R(i, Q){
cur += shf[i];
if (shf[i] < 0){
trn[i+1] = -1;
} else trn[i+1] = 1;
lb[i+1] = max(lb[i], cur);
ub[i+1] = max(ub[i], -cur);
cvrg[i+1] = lb[i+1]+ub[i+1];
}
ans[N-1] += lb[Q];
ans[0] += ub[Q];
F0R(i, N-1){
ll dif = pos[i+1] - pos[i];
int ind = lower_bound(all(cvrg), dif) - cvrg.begin();
if (ind == Q+1) ind = Q;
ll amt = cvrg[ind];
ans[i] += lb[ind];
ans[i+1] += ub[ind];
if (amt > dif){
if (trn[ind] == -1){ // go left, subtract right
ans[i+1] -= amt - dif;
}
else ans[i] -= amt - dif;
}
}
trav(i, ans) cout << i << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
3 ms |
464 KB |
Output is correct |
| 8 |
Correct |
3 ms |
372 KB |
Output is correct |
| 9 |
Correct |
3 ms |
340 KB |
Output is correct |
| 10 |
Correct |
3 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
324 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
3 ms |
468 KB |
Output is correct |
| 16 |
Correct |
3 ms |
456 KB |
Output is correct |
| 17 |
Correct |
3 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
3 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
3 ms |
464 KB |
Output is correct |
| 8 |
Correct |
3 ms |
372 KB |
Output is correct |
| 9 |
Correct |
3 ms |
340 KB |
Output is correct |
| 10 |
Correct |
3 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
324 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
3 ms |
468 KB |
Output is correct |
| 16 |
Correct |
3 ms |
456 KB |
Output is correct |
| 17 |
Correct |
3 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
3 ms |
340 KB |
Output is correct |
| 20 |
Correct |
22 ms |
9428 KB |
Output is correct |
| 21 |
Correct |
21 ms |
9292 KB |
Output is correct |
| 22 |
Correct |
20 ms |
9044 KB |
Output is correct |
| 23 |
Correct |
21 ms |
8932 KB |
Output is correct |
| 24 |
Correct |
42 ms |
9420 KB |
Output is correct |
| 25 |
Correct |
263 ms |
15812 KB |
Output is correct |
| 26 |
Correct |
258 ms |
15696 KB |
Output is correct |
| 27 |
Correct |
262 ms |
15340 KB |
Output is correct |
| 28 |
Correct |
256 ms |
15560 KB |
Output is correct |
| 29 |
Correct |
274 ms |
15044 KB |
Output is correct |
| 30 |
Correct |
250 ms |
14440 KB |
Output is correct |
| 31 |
Correct |
228 ms |
13792 KB |
Output is correct |
| 32 |
Correct |
230 ms |
14020 KB |
Output is correct |
| 33 |
Correct |
26 ms |
1860 KB |
Output is correct |
| 34 |
Correct |
258 ms |
16120 KB |
Output is correct |
| 35 |
Correct |
266 ms |
15636 KB |
Output is correct |
| 36 |
Correct |
260 ms |
15720 KB |
Output is correct |
| 37 |
Correct |
262 ms |
15460 KB |
Output is correct |
| 38 |
Correct |
254 ms |
15336 KB |
Output is correct |
| 39 |
Correct |
252 ms |
15556 KB |
Output is correct |
| 40 |
Correct |
250 ms |
15600 KB |
Output is correct |
| 41 |
Correct |
22 ms |
10052 KB |
Output is correct |
| 42 |
Correct |
228 ms |
14148 KB |
Output is correct |
| 43 |
Correct |
238 ms |
17320 KB |
Output is correct |
| 44 |
Correct |
23 ms |
9932 KB |
Output is correct |
| 45 |
Correct |
231 ms |
15452 KB |
Output is correct |
| 46 |
Correct |
247 ms |
17520 KB |
Output is correct |
| 47 |
Correct |
246 ms |
17608 KB |
Output is correct |
| 48 |
Correct |
252 ms |
17684 KB |
Output is correct |
