#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mpp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define mod 1000000007
#define rep(a, b) for(int a = 0; a < (b); a++)
#define rep2(a, b) for(int a = 1; a < (b); a++)
#define inf 10000000000000000
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vi A(n + 2), B(q);
A[0] = -inf/10;
rep(i, n) {
cin >> A[i + 1];
}
A[n + 1] = inf/10;
rep(i, q) {
cin >> B[i];
}
vi pref(q + 1);
pref[0] = 0;
vi MIN(q + 1), MAX(q + 1), C(q + 1);
MIN[0] = 0;
MAX[0] = 0;
C[0] = -inf;
rep(i, q) {
pref[i + 1] = pref[i] + B[i];
MIN[i + 1] = min(MIN[i], pref[i + 1]);
MAX[i + 1] = max(MAX[i], pref[i + 1]);
C[i + 1] = abs(MIN[i + 1]) + abs(MAX[i + 1]);
}
C.push_back(inf);
rep(i, n) {
ll a = A[i + 1];
ll L = A[i];
ll R = A[i + 2];
ll ANS = 0;
ll l = 0, r = C.size();
ll ans = -1;
while (l + 1 < r) {
ll s = (l + r) / 2;
if (C[s] < a - L || (C[s] == a - L && C[s + 1] == a - L)) {
l = s;
}
else if (C[s] > a - L) {
r = s;
}
else if (C[s] == a - L && (C[s + 1] > a - L)) {
ans = s;
break;
}
}
if (ans == -1) ans = l;
ll index = ans;
ANS += abs(MIN[index]);
if (index + 1 < MIN.size() - 1) {
if (MIN[index] != MIN[index + 1]) {
ANS = ANS + (a - L) - abs(MAX[index]) - abs(MIN[index]);
}
}
l = 0; r = C.size();
ans = -1;
while (l + 1 < r) {
ll s = (l + r) / 2;
if (C[s] < R - a || (C[s] == R - a && C[s + 1] == R - a)) {
l = s;
}
else if (C[s] > R - a) {
r = s;
}
else if (C[s] == R - a && (C[s + 1] > R - a)) {
ans = s;
break;
}
}
if (ans == -1) ans = l;
index = ans;
ANS += abs(MAX[index]);
if (index + 1 <= MAX.size() - 1) {
if (MAX[index] != MAX[index + 1]) {
ANS = ANS + (R - a) - abs(MAX[index]) - abs(MIN[index]);
}
}
cout << ANS << endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:78:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (index + 1 < MIN.size() - 1) {
| ~~~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:101:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if (index + 1 <= MAX.size() - 1) {
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
604 KB |
Output is correct |
| 5 |
Correct |
3 ms |
524 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
856 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
604 KB |
Output is correct |
| 5 |
Correct |
3 ms |
524 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
856 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
