/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#define int long long
#include "candies.h"
using namespace std;
typedef long long ll;
const int N_MAX = 200000;
struct SGTNode {
ll delta;
ll minVal;
ll maxVal;
void setVal (const int &v) {
delta = v;
minVal = min((ll) 0, -delta);
maxVal = max((ll) 0, -delta);
}
};
SGTNode operator + (const SGTNode &u, const SGTNode &v) {
SGTNode w;
w.delta = u.delta + v.delta;
w.minVal = min(v.minVal, -v.delta + u.minVal);
w.maxVal = max(v.maxVal, -v.delta + u.maxVal);
return w;
}
int N;
SGTNode SGT[N_MAX * 4 + 2];
void build (int node, int l, int r) {
if (l == r) {
SGT[node].setVal(0);
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
build(lSon, l, mid);
build(rSon, mid + 1, r);
SGT[node] = SGT[lSon] + SGT[rSon];
}
void build (int n) {
N = n;
build(1, 1, N);
}
void update (int node, int l, int r, int pos, int val) {
if (l == r) {
SGT[node].setVal(val);
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
if (pos <= mid) {
update(lSon, l, mid, pos, val);
} else {
update(rSon, mid + 1, r, pos, val);
}
SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int pos, int val) {
update(1, 1, N, pos + 1, val);
}
ll query (int node, int l, int r, ll currMin, ll currMax, int diff) {
if (l == r) {
ll excess = (max(currMax, SGT[node].maxVal) - min(currMin, SGT[node].minVal)) - diff;
if (SGT[node].delta > 0) {
return +excess;
} else {
return -excess - diff;
}
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
ll minr = min(currMin, SGT[rSon].minVal);
ll maxr = max(currMax, SGT[rSon].maxVal);
if (maxr - minr >= diff) {
return SGT[lSon].delta + query(rSon, mid + 1, r, currMin, currMax, diff);
} else {
return query(lSon, l, mid, minr + SGT[rSon].delta, maxr + SGT[rSon].delta, diff);
}
}
ll query (int diff) {
return query(1, 1, N, 0, 0, diff);
}
vector <signed> distribute_candies (vector <signed> c, vector <signed> l,
vector <signed> r, vector <signed> v) {
int n = (int) c.size();
int q = (int) v.size();
vector <int> evAdd[n], evDel[n];
for (int i = 0; i < q; i++) {
evAdd[l[i]].push_back(i);
evDel[r[i]].push_back(i);
}
build(q);
vector <int> answer (n);
for (int i = 0; i < n; i++) {
for (int j : evAdd[i]) {
update(j, v[j]);
}
answer[i] = SGT[1].delta - query(c[i]);
for (int j : evDel[i]) {
update(j, 0);
}
}
return answer;
}
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:117:12: error: could not convert 'answer' from 'vector<long long int>' to 'vector<int>'
117 | return answer;
| ^~~~~~
| |
| vector<long long int>
