//#include <iostream>
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pi;
typedef tuple<ll, ll, ll> t3i;
typedef tuple<ll, ll, ll, ll> t4i;
typedef tuple<ll, ll, ll, ll, ll> t5i;
typedef vector<pi> vpi;
typedef vector<t3i> vt3i;
typedef vector<t4i> vt4i;
typedef vector<t5i> vt5i;
ll inf = 1000000000000000;
vi none = {-inf, 0, inf, 0, 0};
vvi segtree_M; // max val, max index, min val, min index, update
vpi segtree_M_span; // left, right
// bug: segment tree should be sorted by time, and affect a time-period
void print_tree(ll x) {
//cout << x << ": " << segtree_M[x][0] << " " << segtree_M[x][1] << " " << segtree_M[x][2] << " " << segtree_M[x][3] << " " << segtree_M[x][4] << endl;
if (segtree_M_span[x].first != segtree_M_span[x].second) {
print_tree(2 * x);
print_tree(2 * x + 1);
}
}
vi combine(vi a, vi b) { // if they are equal, second parameter gets dips on index
vi result(5);
if (a[0] > b[0]) {
result[0] = a[0]; result[1] = a[1];
} else {
result[0] = b[0]; result[1] = b[1];
}
if (a[2] < b[2]) {
result[2] = a[2]; result[3] = a[3];
} else {
result[2] = b[2]; result[3] = b[3];
}
return result;
}
void build(ll x, ll l, ll r) {
segtree_M_span[x] = make_pair(l, r);
segtree_M[x] = {0, l, 0, l, 0};
if (l == r) {
return;
}
ll mid = (l + r) / 2;
build(2 * x, l, mid);
build(2 * x + 1, mid + 1, r);
}
void lazy_propagation(ll x) {
// lazy propagation for guaranteed O(log n) for updates
// check if node has children, if so propagate down...
if (segtree_M_span[x].first != segtree_M_span[x].second) {
// left child
segtree_M[2 * x][0] += segtree_M[x][4];
segtree_M[2 * x][2] += segtree_M[x][4];
segtree_M[2 * x][4] += segtree_M[x][4];
// right child
segtree_M[2 * x + 1][0] += segtree_M[x][4];
segtree_M[2 * x + 1][2] += segtree_M[x][4];
segtree_M[2 * x + 1][4] += segtree_M[x][4];
}
segtree_M[x][4] = 0;
}
void update(ll x, ll l, ll r, ll v) { // range update add v to elements of [l, r]
lazy_propagation(x);
if ((segtree_M_span[x].first > r) || (segtree_M_span[x].second < l)) {
return;
}
if ((segtree_M_span[x].first >= l) && (segtree_M_span[x].second <= r)) {
//cout << segtree_M_span[x].first << " " << segtree_M_span[x].second << " : " << v << endl;
segtree_M[x][0] += v;
segtree_M[x][2] += v;
segtree_M[x][4] += v;
return;
}
update(2 * x, l, r, v);
update(2 * x + 1, l, r, v);
segtree_M[x] = combine(segtree_M[2 * x], segtree_M[2 * x + 1]);
}
vi query(ll x, ll l, ll r) {
lazy_propagation(x);
if ((segtree_M_span[x].first > r) || (segtree_M_span[x].second < l)) {
return none;
}
if ((segtree_M_span[x].first >= l) && (segtree_M_span[x].second <= r)) {
return segtree_M[x];
}
return combine(query(2 * x, l, r), query(2 * x + 1, l, r));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
ll n = c.size();
ll q = l.size(); // size of r and v too
std::vector<int> result(n);
vvi queries1(q, vi(4)); // use get<2>(queries[i]) and queries[i] = make_tuple(..., ..., ...)
vvi queries2(q, vi(4));
for (ll i = 0; i < q; i++) {
queries1[i] = {(ll)l[i], (ll)r[i], (ll)v[i], i + 2};
queries2[i] = {(ll)r[i], (ll)l[i], (ll)v[i], i + 2};
}
sort(queries1.begin(), queries1.end());
sort(queries2.begin(), queries2.end());
//cout << "sorted" << endl;
segtree_M.resize(524288); //segtree_M.resize(4 * q + 8);
segtree_M_span.resize(524288); //segtree_M_span.resize(4 * q + 8);
build(1, 0, q + 1);
update(1, 0, 0, inf);
//print_tree(1);
//cout << "built" << endl;
vvi::iterator itr1 = queries1.begin(); // activation ptr
vvi::iterator itr2 = queries2.begin(); // deactivation ptr
for (int i = 0; i < n; i++) {
//cout << i << "/" << n << endl;
// activate queries
if (itr1 != queries1.end()) {
while (itr1->at(0) <= i) {
update(1, itr1->at(3), q + 1, itr1->at(2));
//cout << get<0>(*itr1) << " " << get<1>(*itr1) << " " << get<2>(*itr1) << " " << get<3>(*itr1) << endl;
//print_tree(1);
itr1++;
if (itr1 == queries1.end()) {
break;
}
}
}
//cout << "activated" << endl;
// deactivate queries
if (itr2 != queries2.end()) {
while (itr2->at(0) < i) {
update(1, itr2->at(3), q + 1, -itr2->at(2));
//cout << get<1>(*itr2) << " " << get<0>(*itr2) << " " << get<2>(*itr2) << " " << get<3>(*itr2) << endl;
itr2++;
if (itr2 == queries2.end()) {
break;
}
}
}
//cout << "deactivated" << endl;
//print_tree(1);
//cout << "printed tree" << endl;
// binary search for max - min ≈ c[i]
ll minj = 0;
ll maxj = q + 2;
// store end result outside scope for finishing calculations
vi q_res;
while (minj + 1 < maxj) {
ll midj = (minj + maxj) / 2;
q_res = query(1, midj, q + 1);
//cout << minj << " " << maxj << " " << midj << endl;
//cout << q_res[0] << " " << q_res[1] << " " << q_res[2] << " " << q_res[3] << " " << q_res[4] << endl;
if (q_res[0] - q_res[2] < (ll)c[i]) {
maxj = midj;
} else {
minj = midj;
}
}
q_res = query(1, minj, q + 1);
//cout << minj << endl;
//cout << q_res[0] << " " << q_res[1] << " " << q_res[2] << " " << q_res[3] << " " << q_res[4] << endl;
//cout << "found result" << endl;
// calculate result
if (q_res[1] > q_res[3]) {
// use q_res[1] as reference
result[i] = c[i] + (int)(query(1, q + 1, q + 1)[0] - q_res[0]);
} else {
// use q_res[3] as reference
result[i] = (int)(query(1, q + 1, q + 1)[0] - q_res[2]);
}
//cout << "calculated result: " << result[i] << endl;
}
return result;
}
/*
int main() {
vi c = {10, 15, 13};
vi l = {0, 0};
vi r = {2, 1};
vi v = {20, -11};
vi result = distribute_candies(c, l, r, v);
for (ll i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20820 KB |
Output is correct |
| 3 |
Correct |
16 ms |
21332 KB |
Output is correct |
| 4 |
Correct |
17 ms |
21332 KB |
Output is correct |
| 5 |
Correct |
34 ms |
21316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
74744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
1736 ms |
72528 KB |
Output is correct |
| 3 |
Correct |
2070 ms |
24820 KB |
Output is correct |
| 4 |
Execution timed out |
5063 ms |
74736 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
12 ms |
20820 KB |
Output is correct |
| 3 |
Correct |
1020 ms |
72520 KB |
Output is correct |
| 4 |
Correct |
1920 ms |
23692 KB |
Output is correct |
| 5 |
Execution timed out |
5087 ms |
74828 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20820 KB |
Output is correct |
| 3 |
Correct |
16 ms |
21332 KB |
Output is correct |
| 4 |
Correct |
17 ms |
21332 KB |
Output is correct |
| 5 |
Correct |
34 ms |
21316 KB |
Output is correct |
| 6 |
Execution timed out |
5045 ms |
74744 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
