#include <bits/stdc++.h>
#include <homecoming.h>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 3e4 + 10;
const int block = 320;
const int inf = 1e9;
int n, k, a[maxn], b[maxn];
int lazy[4 * maxn], sec[4 * maxn];
pair <ll, ll> seg[4 * maxn];
void propagate (int, int, int);
void change (int id, int L, int R, int l, int r, int val) {
if (L == l and R == r) {
lazy[id] += val;
seg[id].F += val;
return;
}
propagate (id, L, R);
int mid = (L + R) >> 1;
if (mid > l)
change (2 * id + 0, L, mid, l, min (mid, r), val);
if (mid < r)
change (2 * id + 1, mid, R, max (l, mid), r, val);
seg[id] = max (seg[2 * id + 0], seg[2 * id + 1]);
}
void propagate (int id, int L, int R) {
if (lazy[id] == 0)
return;
int mid = (L + R) >> 1;
change (2 * id + 0, L, mid, L, mid, lazy[id]);
change (2 * id + 1, mid, R, mid, R, lazy[id]);
lazy[id] = 0;
}
void modify (int id, int L, int R, int l, int r) {
if (sec[id] <= 0)
return;
if (L + 1 == R) {
// cout << L << " -> " << b[L] << endl;
if (L + 1 < k) {
change (1, 0, n, 0, L + 1, b[L]);
change (1, 0, n, n - k + L + 1, n, b[L]);
}
else {
change (1, 0, n, L - k + 1, L + 1, b[L]);
}
b[L] = 0;
sec[id] = 0;
return;
}
int mid = (L + R) >> 1;
if (mid > l)
modify (2 * id + 0, L, mid, l, min (mid, r));
if (mid < r)
modify (2 * id + 1, mid, R, max (l, mid), r);
sec[id] = max (sec[2 * id + 0], sec[2 * id + 1]);
}
void build (int id, int L, int R) {
if (L + 1 == R) {
seg[id] = {0, L};
sec[id] = b[L];
return;
}
int mid = (L + R) >> 1;
build (2 * id + 0, L, mid);
build (2 * id + 1, mid, R);
seg[id] = max (seg[2 * id + 0], seg[2 * id + 1]);
sec[id] = max (sec[2 * id + 0], sec[2 * id + 1]);
}
ll solve (int N, int K, int *a, int *b) {
n = N, k = K;
build (1, 0, n);
for (int i = 0; i < n; i++)
change (1, 0, n, i, i + 1, a[i]);
for (int i = 0; i < n; i++) {
if (i + 1 < k) {
change (1, 0, n, 0, i + 1, -b[i]);
change (1, 0, n, n - k + i + 1, n, -b[i]);
}
else {
change (1, 0, n, i - k + 1, i + 1, -b[i]);
}
}
ll ans = 0;
while (true) {
auto it = seg[1];
int idx = it.S;
a[idx] = it.F;
// cout << idx << " " << a[idx] << endl;
if (a[idx] > 0) {
ans += a[idx];
if (idx + k <= n) {
modify (1, 0, n, idx, idx + k);
}
else {
modify (1, 0, n, idx, n);
modify (1, 0, n, 0, (idx + k) - n);
}
change (1, 0, n, idx, idx + 1, -inf);
a[idx] = 0;
}
else {
break;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
17972 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
