#include<bits/stdc++.h>
using namespace std;
long long c[200010];
struct node{long long mini, maxi, lazy;};
const int base = 1<<18;
node tree[2*base];
void push(int w){
if(w>=base)return;
tree[w*2].lazy+=tree[w].lazy;
tree[w*2+1].lazy+=tree[w].lazy;
tree[w*2].mini+=tree[w].lazy;
tree[w*2].maxi+=tree[w].lazy;
tree[w*2+1].mini+=tree[w].lazy;
tree[w*2+1].maxi+=tree[w].lazy;
tree[w].lazy = 0;
}
void update(int w, int l, int p, int a, int b, long long val){
push(w);
if(l>b || p<a)return;
if(a<=l && p<=b){
tree[w].lazy+=val;
tree[w].maxi+=val;
tree[w].mini+=val;
return;
}
update(w*2, l, (l+p)/2, a, b, val);
update(w*2+1, (l+p)/2+1, p, a, b, val);
tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long maxi(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return -1000000000000000000;
if(a<=l && p<=b){
return tree[w].maxi;
}
return max(maxi(w*2, l, (l+p)/2, a, b), maxi(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
long long mini(int w, int l, int p, int a, int b){
push(w);
if(l>b || p<a)return 1000000000000000000;
if(a<=l && p<=b){
return tree[w].mini;
}
return min(mini(w*2, l, (l+p)/2, a, b), mini(w*2+1, (l+p)/2+1, p, a, b));
// tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
// tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}
vector<int> distribute_candies(vector<int>C, vector<int>l, vector<int>r, vector<int> V)
{
vector<int>ans;
int n, q, i, a, b, v;
n = C.size();
for(i=0;i<n;i++)
c[i] = C[i];
q = l.size();
vector<pair<int,pair<int,int>>>sorted;
for(i=1;i<=q;i++){
a = l[i-1];
b = r[i-1];
v = V[i-1];
scanf("%d%d%d", &a, &b, &v);
sorted.push_back({a, {i, v}});
sorted.push_back({b+1, {i, -v}});
}
for(i=q+1;i<base;i++){
tree[base+i].mini = 1000000000000000000;
tree[base+i].maxi = -1000000000000000000;
}
for(i=base-1;i>0;i--){
tree[i].maxi = max(tree[i*2].maxi, tree[i*2+1].maxi);
tree[i].mini = min(tree[i*2].mini, tree[i*2+1].mini);
}
sort(sorted.begin(), sorted.end());
int it = 0;
for(i=0;i<n;i++){
while(it<(int)sorted.size() && sorted[it].first==i){
update(1, 0, base-1, sorted[it].second.first, q, sorted[it].second.second);
it++;
}
int p;
if(tree[1].maxi-tree[1].mini>=c[i]){
int w = 1;
long long sufMAX = -1000000000000000000, sufMIN = 1000000000000000000;
while(w<base){
push(w);
if(max(sufMAX, tree[w*2+1].maxi)-min(sufMIN, tree[w*2+1].mini)>=c[i])
w = w*2+1;
else{
sufMAX = max(sufMAX, tree[w*2+1].maxi);
sufMIN = min(sufMIN, tree[w*2+1].mini);
w = w*2;
}
}
p = w-base;
}
else{
p = -1;
}
if(p==-1)
ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, 0, q));
else{
if(mini(1, 0, base-1, p, q)==mini(1, 0, base-1, p, p))
ans.push_back(mini(1, 0, base-1, q, q)-maxi(1, 0, base-1, p, q)+c[i]);
else
ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, p, q));
}
}
}
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:121:1: warning: no return statement in function returning non-void [-Wreturn-type]
121 | }
| ^
candies.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d%d%d", &a, &b, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
25692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
703 ms |
49732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
25796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
25692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
25692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
