#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
//#define int long long
#define INP freopen("palpath.in","r",stdin)
#define OUTP freopen("palpath.out","w",stdout)
using ld = long double;
using LD = ld;
using namespace std;
const int maxn = 5 * 2e5;
struct node {
long long add;
long long minus;
long long curAdd;
node() {
this->add = 0;
this->minus = 0;
this->curAdd = 0;
}
};
node tree[maxn];
void propogate(int v, int l, int r) {
if (tree[v].curAdd > tree[v].add) {
tree[v].add = tree[v].curAdd;
tree[v].curAdd = 0;
tree[v].minus = 0;
}
if (l == r) return;
if (tree[v].curAdd >= 0) {
tree[v * 2].curAdd += tree[v].curAdd;
tree[v * 2 + 1].curAdd += tree[v].curAdd;
tree[v * 2].minus -= min(tree[v].curAdd, tree[v * 2].minus);
tree[v * 2 + 1].minus -= min(tree[v].curAdd, tree[v * 2 + 1].minus);
tree[v].curAdd = 0;
}
if (tree[v].minus >= 0) {
tree[v * 2].minus += tree[v].minus;
tree[v * 2 + 1].minus += tree[v].minus;
tree[v * 2].curAdd -= min(tree[v].minus, tree[v * 2].curAdd);
tree[v * 2 + 1].curAdd -= min(tree[v].minus, tree[v * 2 + 1].curAdd);
tree[v].minus = 0;
}
}
void applyOp(int v, int val) {
if (val < 0)tree[v].minus+=abs(val);
if (val > 0)tree[v].curAdd+=val;
}
void update(int v, int l, int r, int le, int re, long long val) {
propogate(v, l, r);
if (l > re || r < le) return;
if (l >= le && r <= re) {
applyOp(v, val);
return;
}
int m = (l + r) / 2;
update(v * 2, l, m, le, re, val);
update(v * 2 + 1, m + 1, r, le, re, val);
}
long long getVal(int v, int l, int r, int need, long long c) {
propogate(v, l, r);
if (l == r) {
long long curVal = max(0ll, min(tree[v].add, c) - tree[v].minus);
cout << need << ' ' << tree[v].add << ' ' << tree[v].minus << ' ' << tree[v].curAdd << ' ' << curVal << endl;
if (curVal == 0) curVal+=tree[v].curAdd;
return curVal;
}
int m = (l + r) / 2;
if (need <= m) return getVal(v * 2, l, m, need, c);
else return getVal(v * 2 + 1, m + 1, r, need, c);
}
vector<long long> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
for (int i = 0; i < l.size(); i++) {
int curL = l[i];
int curR = r[i];
long long val = v[i];
update(1, 0, c.size() - 1, curL, curR, val);
//break;
}
vector<long long> ans;
for (int i = 0; i < c.size(); i++) {
ans.push_back(getVal(1, 0, c.size() - 1, i, c[i]));
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
vector<long long> ans = distribute_candies({10, 15, 13}, {0, 0, 0}, {2, 1, 2}, {20, -11, 0});
for (auto a : ans) cout << a << ' ';
return 0;
}
Compilation message
candies.cpp: In function 'std::vector<long long int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < l.size(); i++) {
| ~~^~~~~~~~~~
candies.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccLZyKvd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqMF9kh.o:candies.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
