#include "candies.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
#include <vector>
const int N = 3e5 + 5;
int lz[4 * N], f[N];
pii MX, MN;
struct node{
int hi, idh;
int lo, idl;
} t[4 * N];
node merge(node a, node b) {
node c;
if(a.hi <= b.hi) swap(a, b);
c.hi = a.hi, c.idh = a.idh;
if(a.lo >= b.lo) swap(a, b);
c.lo = a.lo, c.idl = a.idl;
return c;
}
void build(int u,int l,int r) {
if(l == r) {
t[u].idl = t[u].idh = l;
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void push(int u,int l,int r) {
if(!lz[u]) return;
t[u].lo += lz[u]; t[u].hi += lz[u];
if(l != r) {
lz[2 * u] += lz[u];
lz[2 * u + 1] += lz[u];
}
lz[u] = 0; return;
}
void upd(int u, int st, int en, int l, int r,int v) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
if(en == 0) {
t[u].lo = 0, t[u].hi = v;
t[u].idl = t[u].idh = 0;
} else {
lz[u] = v;
push(u, l, r);
}
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, v); upd(2 * u + 1, st, en, mid + 1, r, v);
t[u] = merge(t[2 * u], t[2 * u + 1]);
}
node get(int u, int l, int r, int v) {
push(u, l, r);
int mid = (l + r) / 2;
if(l == r) {
MX = max(MX, {t[u].hi, t[u].idh});
MN = min(MN, {t[u].lo, t[u].idl});
return {MX.f, MX.s, MN.f, MN.s};
}
push(2 * u + 1, l, mid);
if(max(MX.f, t[2 * u + 1].hi) - min(MN.f, t[2 * u + 1].lo) >= v) return get(2 * u + 1, mid + 1, r, v);
MX = max(MX, {t[2 * u + 1].hi, t[2 * u + 1].idh});
MN = min(MN, {t[2 * u + 1].lo, t[2 * u + 1].idl});
return get(2 * u, l, mid, v);
}
void upd(int id, int n, int v) {
for(id; id <= n; id += id & (-id)) f[id] += v;
}
int get(int id) {
int ans = 0;
for(id; id >= 1; id -= id & (-id)) ans += f[id];
return ans;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int q = v.size(), n = c.size();
// vector<int> v[n + 2];
vector<int> ans(n);
vector<int> x(n);
build(1, 0, q);
for(int i = 0; i < q; i++) {
upd(1, i + 1, q, 0, q, v[i]);
upd(i + 1, q, v[i]);
for(int j = l[i]; j <= r[i]; j++) {
x[j] += v[i];
x[j] = min(x[j], c[j]);
x[j] = max(x[j], 0);
}
}
for(int i = 0; i < n; i++) {
upd(1, 0, 0, 0, q, c[i]);
MX = {-1, -1}; MN = {1e9,1e9};
node x = get(1, 0, v.size(), c[i]);
if(x.idl <= x.idh) {
ans[i] = c[i] + get(v.size()) - get(x.idh);
} else ans[i] = get(v.size()) - get(x.idl);
}
return ans;
}
Compilation message
candies.cpp: In function 'void upd(int, int, int)':
candies.cpp:78:9: warning: statement has no effect [-Wunused-value]
78 | for(id; id <= n; id += id & (-id)) f[id] += v;
| ^~
candies.cpp: In function 'int get(int)':
candies.cpp:82:9: warning: statement has no effect [-Wunused-value]
82 | for(id; id >= 1; id -= id & (-id)) ans += f[id];
| ^~
| # |
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 |
Execution timed out |
5063 ms |
17424 KB |
Time limit exceeded |
| 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 |
- |
