#include <bits/stdc++.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};
int 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] = 0;
}
void update(int v, int l, int r, int lo, int hi, int 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; 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]);
}
int query(int v, int l, int r, int lo, int hi, int op) {
prop(v, l, r);
if(l > hi || r < lo) return (op == 0 ? 1e9 + 7 : 0);
if(l >= lo && r <= hi) return (op == 0 ? mn[v] : mx[v]);
int A = query(v * 2, l, (l + r) / 2, lo, hi, op);
int B = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, op);
return (op == 0 ? min(A, B) : max(A, B));
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int N = c.size(), Q = l.size();
vector<int> res(N); vector<pair<int, int>> qs[N + 1];
for(int i = 0; i < Q; i++) {
qs[l[i]].push_back({i, v[i]});
qs[r[i] + 1].push_back({i, -v[i]});
}
for(int i = 0; i < N; i++) {
for(auto u : qs[i]) {
update(1, 0, Q - 1, u.ff, Q - 1, u.ss);
update(1, 0, Q - 1, u.ff, Q - 1, u.ss);
}
int lo = 0, hi = Q - 1, ans = -1;
while(lo <= hi) {
int md = (lo + hi) / 2;
int A = query(1, 0, Q - 1, md, Q - 1, 1);
int B = query(1, 0, Q - 1, md, Q - 1, 0);
if(A - B >= c[i]) lo = md + 1, ans = md;
else hi = md - 1;
}
if(ans == -1) {
res[i] = mx[1] - mn[1];
continue;
}
int A = query(1, 0, Q - 1, ans, Q - 1, 1);
int B = query(1, 0, Q - 1, ans, Q - 1, 0);
int C = query(1, 0, Q - 1, Q - 1, Q - 1, 0);
int D = query(1, 0, Q - 1, ans, ans, 0);
if(D == A) res[i] = C - B;
else res[i] = c[i] + C - A;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2069 ms |
25252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
