#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int int64_t
vector<int> lazy;
vector<pair<pair<int, int>, pair<int, int>>> tree;
void push(int v) {
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
tree[v*2].first.first += lazy[v];
tree[v*2+1].first.first += lazy[v];
tree[v*2].second.first += lazy[v];
tree[v*2+1].second.first += lazy[v];
lazy[v] = 0;
}
void update(int v, int rl, int rr, int ql, int qr, int x) {
push(v);
if (qr < ql) return;
if (rl == ql && rr == qr) {
tree[v].first.first += x;
tree[v].second.first += x;
lazy[v] += x;
return;
}
int rm = (rl + rr) / 2;
update(v*2, rl, rm, ql, min(rm, qr), x);
update(v*2+1, rm+1, rr, max(rm+1, ql), qr, x);
tree[v].first = min(tree[v*2].first, tree[v*2+1].first);
tree[v].second = max(tree[v*2].second, tree[v*2+1].second);
}
pair<pair<int, int>, pair<int, int>> querry(int v, int rl, int rr, int ql, int qr) {
push(v);
if (qr < ql) return {{INT64_MAX, -1}, {INT64_MIN, -1}};
if (rl == ql && rr == qr) {
return tree[v];
}
int rm = (rl + rr) / 2;
pair<pair<int, int>, pair<int, int>> left = querry(v*2, rl, rm, ql, min(rm, qr));
pair<pair<int, int>, pair<int, int>> right = querry(v*2+1, rm+1, rr, max(rm+1, ql), qr);
pair<pair<int, int>, pair<int, int>> res;
res.first = min(left.first, right.first);
res.second = max(left.second, right.second);
return res;
}
void build(int v, int rl, int rr) {
if (rl == rr) {
tree[v] = {{0, rl}, {0, rl}};
}
else {
int rm = (rl + rr) / 2;
build(v*2, rl, rm);
build(v*2+1, rm+1, rr);
}
}
std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l, std::vector<signed> r, std::vector<int> v) {
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
reverse(v.begin(), v.end());
l.push_back(0);
r.push_back(c.size()-1);
v.push_back(0);
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
reverse(v.begin(), v.end());
lazy.assign(l.size()*8, 0);
tree.assign(l.size()*8, {{0, -1}, {0, -1}});
vector<signed> listOfOutputs;
build(1, 0, l.size()-1);
vector<vector<pair<int, bool>>> events(c.size()+1);
for (int i = 0; i<l.size(); i++) {
events[l[i]].push_back({i, 0});
events[r[i]+1].push_back({i, 1});
}
// cout << "EVENTS:\n";
// for (auto i: events) {
// cout << "level\n";
// for (auto j: i)
// cout << j.first << " " << j.second << "\n";
// }
for (int i = 0; i<c.size(); i++) {
for (auto j: events[i]) {
if (j.second) {
update(1, 0, l.size()-1, j.first, l.size()-1, -v[j.first]);
} else {
update(1, 0, l.size()-1, j.first, l.size()-1, v[j.first]);
}
}
int left = 0; int right = l.size()-1;
pair<pair<int, int>, pair<int, int>> res;
while(left<right) {
int m = (left+right) / 2;
res = querry(1, 0, l.size()-1, l.size()-1-m, l.size()-1);
if (res.second.first - res.first.first >= c[i]) right = m;
else left = m+1;
}
res = querry(1, 0, l.size()-1, l.size()-1-left, l.size()-1);
int output;
// cout << res.first.first << " " << res.first.second << " " << res.second.first << " " << res.second.second << "\n";
if (res.second.first - res.first.first >= c[i]) {
if (res.first.second > res.second.second) {
output = querry(1, 0, l.size()-1, l.size()-1, l.size()-1).first.first - res.first.first;
// cout << "min\n";
} else {
output = c[i] - (res.second.first - querry(1, 0, l.size()-1, l.size()-1, l.size()-1).first.first);
// cout << "max\n";
}
} else {
output = querry(1, 0, l.size()-1, l.size()-1, l.size()-1).first.first;
// cout << "other\n";
}
listOfOutputs.push_back(output);
}
return listOfOutputs;
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<long int>)':
candies.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i<l.size(); i++) {
| ~^~~~~~~~~
candies.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int i = 0; i<c.size(); i++) {
| ~^~~~~~~~~
/usr/bin/ld: /tmp/ccJirll9.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `distribute_candies(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
