#include "candies.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cstdio>
using namespace std;
#warning change mxn back
const int mxn = 2e3+5;
using ll = long long;
const ll inf = 2e18;
const ll smaller_inf = 1e18;
struct Node {
ll mx = -inf, mn = inf;
int mxi = -100, mni = -100;
ll tag = 0;
Node() {}
Node(int i) {
mx = mn = 0;
mxi = mni = i;
}
Node join(Node rhs) {
Node lhs = *this;
lhs.tag = 0;
if(rhs.mx > lhs.mx) {
lhs.mx = rhs.mx;
lhs.mxi = rhs.mxi;
}
if(rhs.mn < mn) {
lhs.mn = rhs.mn;
lhs.mni = rhs.mni;
}
return lhs;
}
};
int n, q;
struct Seg {
private:
Node A[4*mxn];
void inc_tag(int u, ll inc) {
A[u].tag += inc;
A[u].mx += inc, A[u].mn += inc;
}
void build(int u, int l, int r) {
if(l == r) {
A[u] = Node(l);
return;
}
int m = (l+r+4)/2-2;
build(2*u, l, m), build(2*u+1, m+1, r);
pull(u);
}
void push(int u) {
inc_tag(2*u, A[u].tag);
inc_tag(2*u+1, A[u].tag);
A[u].tag = 0;
}
void pull(int u) {
A[u] = A[2*u].join(A[2*u+1]);
}
void range_add(int u, int l, int r, int ql, int qr, ll val) {
if(qr < l || ql > r) return;
if(ql <= l && r <= qr) {
inc_tag(u, val);
return;
}
push(u);
int m = (l+r+4)/2-2;
range_add(2*u, l, m, ql, qr, val);
range_add(2*u+1, m+1, r, ql, qr, val);
pull(u);
}
Node get(int u, int l, int r, int ql, int qr) {
if(qr < l || ql > r) return Node{};
if(ql <= l && r <= qr) {
return A[u];
}
push(u);
int m = (l+r+4)/2-2;
return get(2*u, l, m, ql, qr).join(get(2*u+1, m+1, r, ql, qr));
}
public:
void build() {
build(1, -2, q-1);
}
void range_add(int l, int r, ll val) {
range_add(1, -2, q-1, l, r, val);
}
Node get(int l, int r) {
return get(1, -2, q-1, l, r);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
n = c.size();
q = l.size();
vector<int> s(n);
struct Event {
int t, delta;
};
vector<vector<Event>> events(n);
for(int i = 0; i < q; i++) {
events[l[i]].push_back(Event{i, v[i]});
if(r[i] < n-1)
events[r[i]+1].push_back(Event{i, -v[i]});
}
Seg seg;
seg.build();
seg.range_add(-2, q-1, smaller_inf);
seg.range_add(-1, q-1, -smaller_inf);
for(int i = 0; i < n; i++) {
for(auto e : events[i]) {
seg.range_add(e.t, q, e.delta);
}
int lo = -2, hi = q-1;
while(lo < hi) {
int m = (lo+hi+5)/2-2;
auto node = seg.get(m, q-1);
if(node.mx-node.mn < c[i]) {
hi = m-1;
}
else {
lo = m;
}
}
auto node = seg.get(lo, q-1);
if(node.mni < node.mxi) {
// increased, hit max capacity, decreased without going lower than 0
s[i] = c[i]-(node.mx-seg.get(q-1, q-1).mx);
}
else {
// decreased, hit 0, increased without going above capacity
s[i] = seg.get(q-1, q-1).mx-node.mn;
}
}
return s;
}
//namespace Tests {
// void test_segment_tree() {
// Seg s;
// vector<int> arr = {2, 4, 1, 1, -2, 5, 2};
// q = arr.size();
// s.build();
// for(int i = 0; i < (int)arr.size(); i++) {
// s.range_add(i, i, arr[i]);
// }
// for(int i = 0; i < 10; i++) {
// int a = rand() % q, b = rand() % q;
// if(a > b) swap(a, b);
// ll delta = rand()%11-5;
// s.range_add(a, b, delta);
// for(int j = a; j <= b; j++) arr[j] += delta;
// }
// vector<pair<int, int>> ranges;
// for(int i = 0; i < 10; i++) {
// int a = rand() % q, b = rand() % q;
// if(a > b) swap(a, b);
// ranges.push_back({a, b});
// }
// for(auto p : ranges) {
// Node res = s.get(p.first, p.second);
// printf("(%d, %d) max: %lld (%d), min: %lld (%d)\n", p.first, p.second,
// res.mx, res.mxi, res.mn, res.mni);
// auto it_max = max_element(arr.begin()+p.first, arr.begin()+p.second+1);
// auto it_min = min_element(arr.begin()+p.first, arr.begin()+p.second+1);
// assert(res.mx == *it_max);
// assert(res.mn == *it_min);
// assert(res.mxi == distance(arr.begin(), it_max));
// assert(res.mni == distance(arr.begin(), it_min));
// }
// for(int i = 0; i < (int)arr.size(); i++) {
// Node res = s.get(i, i);
// printf("i = %d:\nmax: %lld (%d), min: %lld (%d)\n", i, res.mx, res.mxi, res.mn, res.mni);
// }
// }
//}
Compilation message
candies.cpp:10:2: warning: #warning change mxn back [-Wcpp]
10 | #warning change mxn back
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
696 KB |
Output is correct |
| 5 |
Correct |
5 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
39380 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Runtime error |
62 ms |
20012 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Runtime error |
50 ms |
16572 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
696 KB |
Output is correct |
| 5 |
Correct |
5 ms |
768 KB |
Output is correct |
| 6 |
Runtime error |
103 ms |
39380 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
