#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
using ll = long long;
ll maxll = (1ll << 62);
ll minll = -maxll;
ll lseg = 0;
ll rseg;
class name {
public:
ll value = 0;
ll pos = -1;
};
class segtree {
public:
name max_value;
name min_value;
ll total_pus_max = 0;
ll total_pus_min = 0;
segtree* left = nullptr;
segtree* right = nullptr;
};
void add_max(segtree* seg, ll left, ll right, ll s, ll e, ll number, ll total_pus = 0) {
if (s <= left && right <= e) {
seg->max_value.value += (number + total_pus);
seg->total_pus_max += (number + total_pus);
if (seg->max_value.pos == -1)
seg->max_value.pos = left;
return;
}
if (left > e || right < s) {
seg->max_value.value += total_pus;
seg->total_pus_max += total_pus;
if (seg->max_value.pos == -1)
seg->max_value.pos = left;
return;
}
int mid = (left + right) / 2;
total_pus += seg->total_pus_max;
seg->total_pus_max = 0;
if (seg->left == nullptr)
seg->left = new segtree;
if (seg->right == nullptr)
seg->right = new segtree;
add_max(seg->left, left, mid, s, e, number, total_pus);
add_max(seg->right, mid + 1, right, s, e, number, total_pus);
if (seg->left->max_value.value >= seg->right->max_value.value) {
seg->max_value.value = seg->left->max_value.value;
seg->max_value.pos = seg->left->max_value.pos;
}
else {
seg->max_value.value = seg->right->max_value.value;
seg->max_value.pos = seg->right->max_value.pos;
}
}
void add_min(segtree* seg, ll left, ll right, ll s, ll e, ll number, ll total_pus = 0) {
if (s <= left && right <= e) {
seg->min_value.value += (number + total_pus);
seg->total_pus_min += (number + total_pus);
if (seg->min_value.pos == -1)
seg->min_value.pos = left;
return;
}
if (left > e || right < s) {
seg->min_value.value += total_pus;
seg->total_pus_min += total_pus;
if (seg->min_value.pos == -1)
seg->min_value.pos = left;
return;
}
int mid = (left + right) / 2;
total_pus += seg->total_pus_min;
seg->total_pus_min = 0;
if (seg->left == nullptr)
seg->left = new segtree;
if (seg->right == nullptr)
seg->right = new segtree;
add_min(seg->left, left, mid, s, e, number, total_pus);
add_min(seg->right, mid + 1, right, s, e, number, total_pus);
if (seg->left->min_value.value <= seg->right->min_value.value) {
seg->min_value.value = seg->left->min_value.value;
seg->min_value.pos = seg->left->min_value.pos;
}
else {
seg->min_value.value = seg->right->min_value.value;
seg->min_value.pos = seg->right->min_value.pos;
}
}
name get_max(segtree* seg, ll left, ll right, ll s, ll e) {
if (seg == nullptr)
return { 0,left };
if (s <= left && right <= e)
return { seg->max_value.value,seg->max_value.pos };
if (left > e || right < s)
return { minll,left };
int mid = (right + left) / 2;
name get1 = get_max(seg->left, left, mid, s, e);
name get2 = get_max(seg->right, mid + 1, right, s, e);
if (get1.value >= get2.value) {
get1.value += seg->total_pus_max;
return get1;
}
else {
get2.value += seg->total_pus_max;
return get2;
}
}
name get_min(segtree* seg, ll left, ll right, ll s, ll e) {
if (seg == nullptr)
return { 0,left };
if (s <= left && right <= e)
return { seg->min_value.value,seg->min_value.pos };
if (left > e || right < s)
return { maxll,left };
int mid = (right + left) / 2;
name get1 = get_min(seg->left, left, mid, s, e);
name get2 = get_min(seg->right, mid + 1, right, s, e);
if (get1.value <= get2.value) {
get1.value += seg->total_pus_min;
return get1;
}
else {
get2.value += seg->total_pus_min;
return get2;
}
}
class Query {
public:
ll t;
ll pos;
ll c;
bool operator<(const Query b) const {
return pos < b.pos;
}
}put_in;
std::vector<Query> Q;
std::vector<int> result;
segtree* seg = new segtree;
name bsearch_max(int c) {
int L = -1;
int R = rseg - 1;
while (R - L > 1) {
int mid = (R + L) / 2;
name get1 = get_max(seg, lseg, rseg, mid, rseg);
name get2 = get_min(seg, lseg, rseg, get1.pos, rseg);
if (get1.value - get2.value <= c) {
R = mid;
}
else
L = mid;
}
return get_max(seg,lseg,rseg,R,rseg);
}
name bsearch_min(int c) {
int L = -1;
int R = rseg - 1;
while (R - L > 1) {
int mid = (R + L) / 2;
name get1 = get_min(seg, lseg, rseg, mid, rseg);
name get2 = get_max(seg, lseg, rseg, get1.pos, rseg);
if (get2.value - get1.value <= c) {
R = mid;
}
else
L = mid;
}
return get_min(seg, lseg, rseg, R, rseg);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
add_max(seg, lseg, rseg, 0, 0, 0);
add_min(seg, lseg, rseg, 0, 0, 0);
rseg = v.size() + 1;
for (int q = 0; q < l.size(); q++) {
put_in.t = q + 1;
put_in.c = v[q];
put_in.pos = l[q];
Q.push_back(put_in);
put_in.t = q + 1;
put_in.c = -v[q];
put_in.pos = r[q] + 1;
Q.push_back(put_in);
}
std::sort(Q.begin(), Q.end());
int i = 0;
for (int q = 0; q < c.size(); q++) {
if (i < Q.size()) {
while (Q[i].pos == q) {
add_max(seg, lseg, rseg, Q[i].t, rseg, Q[i].c);
add_min(seg, lseg, rseg, Q[i].t, rseg, Q[i].c);
++i;
if (i >= Q.size())
break;
}
}
name get1 = bsearch_max(c[q]);
name get2 = bsearch_min(c[q]);
if (get1.pos < get2.pos) {
result.push_back(c[q] + get_max(seg, lseg, rseg, rseg, rseg).value - get1.value);
}
else if (get1.pos == get2.pos) {
if (get1.value >= c[q])
result.push_back(c[q]);
else
result.push_back(0);
}
else {
result.push_back(get_max(seg, lseg, rseg, rseg, rseg).value - get2.value);
}
}
return result;
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:175:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for (int q = 0; q < l.size(); q++) {
| ~~^~~~~~~~~~
candies.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for (int q = 0; q < c.size(); q++) {
| ~~^~~~~~~~~~
candies.cpp:188:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | if (i < Q.size()) {
| ~~^~~~~~~~~~
candies.cpp:193:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | if (i >= Q.size())
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2567 ms |
53736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 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 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
