#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7FFFFFFF
#define ff first
#define ss second
struct info {
ll mn, mx, sm, mnp, mxp;
info() : mn(inf), mx(-inf), sm(0), mnp(-1), mxp(-1){};
info(ll p) : mn(inf), mx(-inf), sm(0), mnp(p), mxp(p){};
info(ll v, ll p) : mn(v), mx(v), sm(v), mnp(p), mxp(p){};
};
struct node {
ll l, r; // mleft, right
info d;
node() : node(-1, -1){};
node(ll l, ll r) : l(l), r(r){};
};
struct st {
vector<node> t;
const ll n;
st(ll n) : t(n * 4), n(n) { build(0, n - 1, 0); }
void build(ll l, ll r, ll x) {
t[x] = node(l, r);
if (l == r) t[x].d = info(l);
if (l == r) return;
ll m = l + r >> 1;
build(l, m, x * 2 + 1);
build(m + 1, r, x * 2 + 2);
merge(x);
}
void upd(ll i, ll v, ll x = 0) {
if (t[x].l > i || t[x].r < i) return;
if (t[x].l == t[x].r) {
t[x].d = info(v, i);
return;
}
upd(i, v, x * 2 + 1);
upd(i, v, x * 2 + 2);
merge(x);
}
ll q(ll c) {
info d = query(c);
cout << "uwu: " << d.mnp << " " << d.mxp << " " << d.mn << " " << d.mx << endl;
if (d.mnp < d.mxp) {
// touches top wall??
return c + sum(d.mxp + 1, n - 1);
} else {
return sum(d.mnp + 1, n - 1);
}
}
ll sum(ll l, ll r, ll x = 0) {
if (t[x].l > r || t[x].r < l) return 0;
if (t[x].l >= l && t[x].r <= r) return t[x].d.sm;
return sum(l, r, x * 2 + 1) + sum(l, r, x * 2 + 2);
}
info query(ll c, info d = info(), ll x = 0) {
if (t[x].l == t[x].r) return merge(t[x].d, d);
info tmp = merge(t[x * 2 + 2].d, d);
if (tmp.mx - tmp.mn >= c) {
return query(c, d, x * 2 + 2);
}
return query(c, tmp, x * 2 + 1);
}
void merge(ll x) {
t[x].d = merge(t[x * 2 + 1].d, t[x * 2 + 2].d);
}
info merge(info a, info b) {
info c;
c.sm = a.sm + b.sm;
if (a.mn < a.sm + b.mn) {
c.mn = a.mn;
c.mnp = a.mnp;
} else {
c.mn = a.sm + b.mn;
c.mnp = b.mnp;
}
if (a.mx > a.sm + b.mx) {
c.mx = a.mx;
c.mxp = a.mxp;
} else {
c.mx = a.sm + b.mx;
c.mxp = b.mxp;
}
return c;
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
const ll n = c.size();
const ll q = l.size();
std::vector<int> s(n);
st ac(q + 2);
ac.upd(0, inf);
ac.upd(1, -inf);
vector<vector<pair<int, int>>> qs(n + 1);
for (int i = 0; i < q; i++) {
qs[l[i]].push_back({i + 2, v[i]});
qs[r[i] + 1].push_back({i + 2, 0});
}
for (int i = 0; i < n; i++) {
for (auto &x : qs[i])
ac.upd(x.ff, x.ss);
s[i] = ac.q(c[i]);
}
return s;
}
Compilation message
candies.cpp: In member function 'void st::build(long long int, long long int, long long int)':
candies.cpp:32:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | ll m = l + r >> 1;
| ~~^~~
| # |
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 |
815 ms |
70676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
