#include "candies.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ar array
#define pii pair<int, int>
#define vi vector<int>
#define sz(s) (int) s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define fi first
#define se second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define trav(x, a) for (auto& (x) : (a))
typedef long long ll;
typedef unsigned long long ull;
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
const ll inf = 1ll << 60;
struct SegTree {
int lo, mi, hi;
ll save;
pair<ll, int> mnval, mxval;
SegTree *l, *r;
SegTree(int lo, int hi) {
mi = lo + hi >> 1;
save = 0;
mnval = mxval = {0, lo};
if (lo != hi) {
l = new SegTree(lo, mi);
r = new SegTree(mi + 1, hi);
}
}
void pushdown() {
if (save) {
l -> mnval.fi += save;
l -> mxval.fi += save;
l -> save += save;
r -> mnval.fi += save;
r -> mxval.fi += save;
r -> save += save;
save = 0;
}
}
void upd(int x, int y, ll val) {
if (lo == x && hi == y) {
mnval.fi += val;
mxval.fi += val;
save += val;
} else {
pushdown();
if (x <= mi)
l -> upd(x, min(y, mi), val);
else
r -> upd(max(x, mi + 1), y, val);
}
}
int find(ll diff, ll curmx, ll curmn) {
if (max(mxval.fi, curmx) - min(mnval.fi, curmn) < diff)
return -1;
if (lo == hi)
return lo;
pushdown();
if (max(r -> mxval.fi, curmx) - min(r -> mnval.fi, curmn) >= diff)
return r -> find(diff, curmx, curmn);
return l -> find(diff, max(curmx, r -> mxval.fi), min(curmn, r -> mnval.fi));
}
pair<ll, int> getmn(int x, int y) {
if (lo == x && hi == y)
return mnval;
pushdown();
auto u = x <= mi ? l -> getmn(x, min(y, mi)) : make_pair(inf, -1);
auto v = mi < y ? r -> getmn(max(x, mi + 1), y) : make_pair(inf, -1);
return min(u, v);
}
pair<ll, int> getmx(int x, int y) {
if (lo == x && hi == y)
return mxval;
pushdown();
auto u = x <= mi ? l -> getmx(x, min(y, mi)) : make_pair(-inf, -1);
auto v = mi < y ? r -> getmx(max(x, mi + 1), y) : make_pair(-inf, -1);
return max(u, v);
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = sz(c), q = sz(l);
vector<vi> queries(n, vi());
rep(i, 0, q) {
queries[l[i]].pb(i + 1);
if (r[i] + 1 < n)
queries[r[i] + 1].pb(-i - 1);
}
SegTree* tree = new SegTree(0, q);
vi ans;
rep(i, 0, n) {
trav(id, queries[i]) {
if (id < 0) tree -> upd(-id, q, -v[-id - 1]);
else tree -> upd(id, q, v[id - 1]);
}
int u = tree -> find(c[i], -inf, inf);
auto [vlst, _] = tree -> getmn(q, q);
auto [vmn, idmn] = tree -> getmn(max(u, 0), q);
if (u < 0) ans.pb(vlst - vmn);
else {
auto [vmx, idmx] = tree -> getmx(u, q);
if (idmx > idmn) ans.pb(c[i] - vmx + vlst);
else ans.pb(vlst - vmn);
}
}
return ans;
}
Compilation message
candies.cpp: In constructor 'SegTree::SegTree(int, int)':
candies.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | mi = lo + hi >> 1;
| ~~~^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:19:31: warning: unnecessary parentheses in declaration of 'id' [-Wparentheses]
19 | #define trav(x, a) for (auto& (x) : (a))
| ^
candies.cpp:115:5: note: in expansion of macro 'trav'
115 | trav(id, queries[i]) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
222 ms |
98024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
