#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef pair<long long, int> plli;
struct segTree{
struct node{
plli mxm, mnm;
long long lazy;
};
vector<node> t;
int maxN;
segTree(int n){
maxN = (1<<((int)log2(n)+1));
t.resize(2*maxN);
for(int i = maxN; i < t.size(); i++)
t[i].mxm = {0, i-maxN}, t[i].mnm = {0, i-maxN};
for(int i = maxN; i > 0; i--)
t[i].mxm = max(t[i*2].mxm, t[i*2+1].mxm), t[i].mnm = min(t[i*2].mnm, t[i*2+1].mnm);
}
void upd(int v, long long val){
t[v].lazy += val, t[v].mxm.first += val, t[v].mnm.first += val;
}
void push(int v){
upd(v*2, t[v].lazy), upd(v*2+1, t[v].lazy);
t[v].lazy = 0;
}
void add(int pos, long long val){
add(1, pos, maxN, 0, maxN, val);
}
void add(int v, int ll, int rr, int l, int r, long long val){
if(min(r, rr) <= max(l, ll)) return;
if(ll <= l && r <= rr){
upd(v, val);
return;
}
push(v);
int m = (l+r)/2;
add(v*2, ll, rr, l, m, val), add(v*2+1, ll, rr, m, r, val);
t[v].mnm = min(t[v*2].mnm, t[v*2+1].mnm);
t[v].mxm = max(t[v*2].mxm, t[v*2+1].mxm);
}
pair<plli, plli > find(long long c){
return find(1, c, {-1e18, -1}, {1e18, -1});
}
pair<plli, plli > find(int v, long long c, plli mxm, plli mnm){
if(v >= maxN)
return {max(mxm, t[v].mxm), min(mnm, t[v].mnm)};
push(v);
plli mxm2 = max(mxm, t[v*2+1].mxm), mnm2 = min(t[v*2+1].mnm, mnm);
if(mxm2.first - mnm2.first >= c) return find(v*2+1, c, mxm, mnm);
return find(2*v, c, mxm2, mnm2);
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = l.size();
std::vector<int> s(c.size());
segTree t = segTree(n+2);
t.add(0, 1e9+7), t.add(1, -1e9-7);
vector<vector<plli> > diff(c.size()+1);
long long sum = 0;
for(int i = 0; i < n; i++){
diff[l[i]].push_back({v[i], i+2});
diff[r[i]+1].push_back({-v[i], i+2});
}
for(int i = 0; i < c.size(); i++){
for(plli& a : diff[i]) t.add(a.second, a.first), sum += a.first;
auto [mxm, mnm] = t.find(c[i]);
// cout << mxm.first << " " << mxm.second << " " << mnm.first << " " << mnm.second << "\n";
// cout << sum << "\n";
if(mxm.second < mnm.second)
s[i] = sum - mnm.first;
else
s[i] = c[i] - (mxm.first - sum);
}
return s;
}
/*int main(){
distribute_candies({10, 15, 13}, {0, 0}, {1, 2}, {20, -11});
}*/
Compilation message
candies.cpp: In constructor 'segTree::segTree(int)':
candies.cpp:16:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = maxN; i < t.size(); i++)
| ~~^~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < c.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
323 ms |
43160 KB |
Output is correct |
| 2 |
Correct |
328 ms |
47248 KB |
Output is correct |
| 3 |
Correct |
321 ms |
47076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
