#include <bits/stdc++.h>
#include "candies.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int MOD = 998244353;
const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};
ll mn[800005], mx[800005], lazy[800005];
void prop(int v, int l, int r) {
if(l == r) return;
mn[v * 2] += lazy[v];
mn[v * 2 + 1] += lazy[v];
mx[v * 2] += lazy[v];
mx[v * 2 + 1] += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int l, int r, int lo, int hi, ll val) {
prop(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
mn[v] += val; mx[v] += val;
lazy[v] += val; prop(v, l, r);
return;
}
update(v * 2, l, (l + r) / 2, lo, hi, val);
update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
ll getMin(int v, int l, int r, int lo) {
prop(v, l, r);
if(r < lo) return 1e9 + 7;
if(l >= lo) return mn[v];
return min(getMin(v * 2, l, (l + r) / 2, lo),
getMin(v * 2 + 1, (l + r) / 2 + 1, r, lo));
}
ll getMax(int v, int l, int r, int lo) {
prop(v, l, r);
if(r < lo) return -1e9 - 7;
if(l >= lo) return mx[v];
return max(getMax(v * 2, l, (l + r) / 2, lo),
getMax(v * 2 + 1, (l + r) / 2 + 1, r, lo));
}
ll getPos(int v, int l, int r, int p) {
prop(v, l, r);
if(l == r) return mx[v];
int md = (l + r) / 2;
if(p <= md) return getPos(v * 2, l, md, p);
return getPos(v * 2 + 1, md + 1, r, p);
}
vector<int> distribute_candies(vector <int> C, vector <int> L,
vector <int> R, vector <int> V) {
int N = C.size(), Q = V.size();
vector<pair<int, int>> qs[2 * N];
for(int l = 0; l < Q; l++) {
qs[L[l]].push_back({l + 1, V[l]});
qs[R[l] + 1].push_back({l + 1, -V[l]});
}
vector<int> res(N);
for(int l = 0; l < N; l++) {
for(auto u : qs[l])
update(1, 0, Q, u.first, Q, u.second);
if(getMax(1, 0, Q, 0) - getMin(1, 0, Q, 0) < C[l]) {
res[l] = getMax(1, 0, Q, Q) - getMin(1, 0, Q, 0);
continue;
}
int lo = 0, hi = Q, ans = 0;
while(lo <= hi) {
int md = (lo + hi) / 2;
if(getMax(1, 0, Q, md) - getMin(1, 0, Q, md) >= C[l]) {
lo = md + 1; ans = md;
}
else hi = md - 1;
}
ll A = getMax(1, 0, Q, Q), B = getPos(1, 0, A, ans);
ll mn = getMin(1, 0, Q, ans), mx = getMax(1, 0, Q, ans);
if(B == mx) res[l] = A - mn;
else res[l] = C[l] + A - mx;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
52376 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
