#include "candies.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef tuple<ll, pair<ll, int>, pair<ll, int>> Entry;
struct SegTree {
int n = -1, N = -1;
vector<Entry> tree; //sum, min, max
Entry id = { 0, {LLONG_MAX, 0}, {0, 0}};
SegTree(int _n) {
n = _n;
N = 1;
while (N < n) N *= 2;
tree.resize(2 * N, id);
}
Entry merge(Entry a, Entry b) {
auto [s1, min1, max1] = a;
auto [s2, min2, max2] = b;
int s = s1 + s2;
ii mn;
if (min1.first < min2.first) {
mn.first = min1.first;
mn.second = min1.second;
}
else {
mn.first = min2.first;
mn.second = min2.second;
}
ii mx;
if (max1.first > max2.first) {
mx.first = max1.first;
mx.second = max1.second;
}
else {
mx.first = max2.first;
mx.second = max2.second;
}
return {s, mn, mx};
}
void set(int idx, const Entry& v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tr - tl == 1) {
tree[i] = v;
return;
}
int tm = (tl + tr) / 2;
if (idx < tm) {
set(idx, v, 2 * i, tl, tm);
}
else {
set(idx, v, 2 * i + 1, tm, tr);
}
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
Entry get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (l >= tr || r <= tl)
return id;
if (tl >= l && tr <= r)
return tree[i];
int tm = (tl + tr) / 2;
return merge(get(l, r, 2 * i, tl, tm), get(l, r, 2 * i + 1, tm, tr));
}
};
vi distribute_candies(vi c, vi ls, vi rs, vi vs) {
int n = c.size();
int q = ls.size();
SegTree segTree(q + 1);
vvii queryStarts(n), queryEnds(n);
loop(i, q) {
int l = ls[i];
int r = rs[i];
int v = vs[i];
queryStarts[l].push_back({v, i + 1});
queryEnds[r].push_back({v, i + 1});
}
vi s(n);
loop(i, n) {
for (auto [v, idx] : queryStarts[i]) {
segTree.set(idx, {v, {v, idx}, {v, idx}});
}
segTree.set(0, {0, {0, 0}, {c[i], 0}});
int l = 0, r = q;
while (l < r) {
int m = (l + r + 1) / 2;
//ll diff = sufMax[m].first - sufMin[m].first;
auto [sum, mn, mx] = segTree.get(m, q + 1);
ll diff = mx.first - mn.first;
if (diff < c[i]) {
r = m - 1;
}
else {
l = m;
}
}
if (l == 0) {
//s[i] = cumul.back();
s[i] = get<0>(segTree.get(0, q + 1));
}
else {
//int lastMin = sufMin[l].second;
//int lastMax = sufMax[l].second;
auto [sum, mn, mx] = segTree.get(l, q + 1);
int lastMin = mn.second;
int lastMax = mx.second;
if (lastMin >= lastMax) {
l = lastMin;
s[i] = 0;
}
else {
l = lastMax;
s[i] = c[i];
}
//s[i] += cumul.back() - cumul[l];
ll extra = get<0>(segTree.get(l + 1, q + 1));
s[i] += extra;
}
for (auto [v, idx] : queryEnds[i]) {
segTree.set(idx, segTree.id);
}
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1145 ms |
49748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
