| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 400191 |
2021-05-07T14:22:07 Z |
nvmdava |
Snowball (JOI21_ho_t2) |
C++17 |
|
142 ms |
12080 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 200005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll x[N];
vector<ll> loc;
ll ans[N];
bool sign(ll a, ll b){
if(a > 0 && b > 0) return 1;
if(a < 0 && b < 0) return 1;
return 0;
}
ll get(ll a){
int l = 1;
int r = loc.size() - 1;
if(sign(loc[r], a) && abs(loc[r]) + abs(loc[r - 1]) <= abs(a))
return abs(loc[r]);
if(r <= 1){
if(sign(loc[r], a))
return abs(a);
return 0;
}
if(sign(loc[r - 1], a) && abs(loc[r - 1]) + abs(loc[r - 2]) <= abs(a))
return abs(loc[r - 1]);
while(l != r){
int m = (l + r) >> 1;
if(abs(loc[m]) + abs(loc[m - 1]) >= abs(a)){
r = m;
} else {
l = m + 1;
}
}
int m = l;
if(sign(loc[m], a))
return abs(a + loc[m - 1]);
else
return abs(loc[m - 1]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin>>n>>q;
for(int i = 1; i <= n; ++i)
cin>>x[i];
ll now = 0;
loc.push_back(0);
while(q--){
ll t;
cin>>t;
now += t;
if(now == 0) continue;
if(sign(now, loc.back())){
if(abs(now) > abs(loc.back())){
loc.pop_back();
loc.push_back(now);
}
} else {
if(loc.size() <= 2 || abs(loc[loc.size() - 2]) < abs(now)){
loc.push_back(now);
}
}
}
for(int i = 1; i < n; ++i){
ans[i] += get(x[i + 1] - x[i]);
ans[i + 1] += get(x[i] - x[i + 1]);
}
ans[n] += get(1'000'000'000'000'000'000);
ans[1] += get(-1'000'000'000'000'000'000);
for(int i = 1; i <= n; ++i)
cout<<ans[i]<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
336 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
2 ms |
368 KB |
Output is correct |
| 16 |
Correct |
2 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
2 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
336 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
2 ms |
368 KB |
Output is correct |
| 16 |
Correct |
2 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
2 ms |
336 KB |
Output is correct |
| 20 |
Correct |
32 ms |
3268 KB |
Output is correct |
| 21 |
Correct |
30 ms |
3144 KB |
Output is correct |
| 22 |
Correct |
30 ms |
2892 KB |
Output is correct |
| 23 |
Correct |
28 ms |
2768 KB |
Output is correct |
| 24 |
Correct |
37 ms |
3408 KB |
Output is correct |
| 25 |
Correct |
142 ms |
9676 KB |
Output is correct |
| 26 |
Correct |
140 ms |
9528 KB |
Output is correct |
| 27 |
Correct |
134 ms |
9200 KB |
Output is correct |
| 28 |
Correct |
138 ms |
9276 KB |
Output is correct |
| 29 |
Correct |
128 ms |
8424 KB |
Output is correct |
| 30 |
Correct |
104 ms |
7316 KB |
Output is correct |
| 31 |
Correct |
70 ms |
6812 KB |
Output is correct |
| 32 |
Correct |
63 ms |
6956 KB |
Output is correct |
| 33 |
Correct |
15 ms |
1356 KB |
Output is correct |
| 34 |
Correct |
124 ms |
9216 KB |
Output is correct |
| 35 |
Correct |
120 ms |
8804 KB |
Output is correct |
| 36 |
Correct |
142 ms |
9536 KB |
Output is correct |
| 37 |
Correct |
136 ms |
9204 KB |
Output is correct |
| 38 |
Correct |
142 ms |
9156 KB |
Output is correct |
| 39 |
Correct |
134 ms |
9324 KB |
Output is correct |
| 40 |
Correct |
99 ms |
9376 KB |
Output is correct |
| 41 |
Correct |
31 ms |
3008 KB |
Output is correct |
| 42 |
Correct |
63 ms |
6992 KB |
Output is correct |
| 43 |
Correct |
104 ms |
12064 KB |
Output is correct |
| 44 |
Correct |
35 ms |
4608 KB |
Output is correct |
| 45 |
Correct |
73 ms |
9268 KB |
Output is correct |
| 46 |
Correct |
105 ms |
12080 KB |
Output is correct |
| 47 |
Correct |
99 ms |
10620 KB |
Output is correct |
| 48 |
Correct |
99 ms |
10640 KB |
Output is correct |
