# include <bits/stdc++.h>
#include "candies.h"
#define f first
#define s second
#define pb push_back
#define pii pair <long long, long long>
using namespace std;
const int N = 3e5 + 5;
long long n,q,l[N],r[N],val[N],idx,c[N],le,ri,mid,mxid,mnid,ans,cc1;
vector < pii > v[N];
int lazy[4*N];
struct nd {
long long mx;
long long mn;
long long mxidx;
long long mnidx;
long long sum;
};
nd tree[4*N],emp;
nd merge(nd a, nd b) {
nd ans;
ans.mx = max(a.mx,b.mx);
ans.mn = min(a.mn,b.mn);
if (a.mx >= b.mx) ans.mxidx = a.mxidx;
else ans.mxidx = b.mxidx;
if (a.mn <= b.mn) ans.mnidx = a.mnidx;
else ans.mnidx = b.mnidx;
ans.sum = a.sum + b.sum;
return ans;
}
void build(int node, int le, int ri) {
if (le == ri) {
tree[node].mx = 0;
tree[node].mn = 0;
tree[node].mxidx = le;
tree[node].mnidx = le;
tree[node].sum = 0;
return ;
}
int mid = (le + ri) / 2;
build(2*node, le, mid);
build(2*node + 1, mid + 1, ri);
tree[node] = merge(tree[2*node],tree[2*node + 1]);
}
void update(int node, int le, int ri, int start, int end, int val) {
if (lazy[node]) {
tree[node].mx += lazy[node];
tree[node].mn += lazy[node];
tree[node].sum += (ri - le + 1) * lazy[node];
if (le != ri) {
lazy[2*node] += lazy[node];
lazy[2*node + 1] += lazy[node];
}
lazy[node] = 0;
}
if (le > end || ri < start) return ;
if (le >= start && ri <= end) {
tree[node].mx += val;
tree[node].mn += val;
tree[node].sum += (ri - le + 1) * val;
if (le != ri) {
lazy[2*node] += val;
lazy[2*node + 1] += val;
}
return ;
}
int mid = (le + ri) / 2;
update(2*node, le, mid ,start,end,val);
update(2*node + 1, mid + 1, ri, start,end, val);
tree[node] = merge(tree[2*node],tree[2*node + 1]);
}
nd getans(int node, int le, int ri, int start, int end) {
if (lazy[node]) {
tree[node].mx += lazy[node];
tree[node].mn += lazy[node];
tree[node].sum += (ri - le + 1) * lazy[node];
if (le != ri) {
lazy[2*node] += lazy[node];
lazy[2*node + 1] += lazy[node];
}
lazy[node] = 0;
}
if (le > end || ri < start) return emp;
if (le >= start && ri <= end) {
return tree[node];
}
int mid = (le + ri) / 2;
return merge(getans(2*node,le,mid,start,end), getans(2*node + 1, mid + 1, ri, start,end));
}
int check(int mid) {
if (getans(1,0,q,mid,q).mx - getans(1,0,q,mid,q).mn >= cc1) return 1;
else return 0;
}
vector<int> distribute_candies(vector<int> cc, vector<int> ll, vector<int> rr, vector<int> vall) {
n = cc.size();
for (int i = 1; i <= n; i++) {
c[i] = cc[i - 1];
}
emp.mx = -1e9;
vector <int> anss;
anss.clear();
emp.mn = 1e9;
emp.sum = 0;
q = ll.size();
for (int i = 1; i <= q; i++) {
l[i] = ll[i - 1];
r[i] = rr[i - 1];
val[i] = vall[i - 1];
l[i]++;
r[i]++;
v[l[i]].pb({i,val[i]});
v[r[i] + 1].pb({i,-val[i]});
}
build(1,0,q);
for (int i = 1; i <= n; i++) {
//cout<<"s"<<endl;
for (int j = 0; j < v[i].size(); j++) {
idx = v[i][j].f;
//if (abs(v[i][j].s) == 26416) {
update(1,0,q,idx,q,v[i][j].s);
//cout<<idx<<" "<<q<<" "<<v[i][j].s<<endl;
//}
}
le = 0; ri = q;
cc1 = c[i];
ans = -1;
while (le <= ri) {
mid = (le + ri) / 2;
if (check(mid)) {
ans = mid;
le = mid + 1;
} else ri = mid - 1;
}
if (ans == -1) {
if (getans(1,0,q,0,q).mn < 0) {
int leeid = getans(1,0,q,0,q).mnidx;
anss.pb(getans(1,0,q,q,q).sum - getans(1,0,q,leeid,leeid).sum);
continue;
}
anss.pb(getans(1,0,q,q,q).sum);//<<endl;
continue;
}
int mnval = getans(1,0,q,ans,q).mn;
mnid = getans(1,0,q,ans,q).mnidx;
int mxval = getans(1,0,q,ans,q).mx;
mxid = getans(1,0,q,ans,q).mxidx;
if (mnid >= mxid) {
le = mnid;
ri = q;
int leeid = getans(1,0,q,mnid,q).mnidx;
anss.pb(getans(1,0,q,q,q).sum-getans(1,0,q,leeid,leeid).sum);//<<endl;
} else {
le = mxid;
ri = q;
int leeid = getans(1,0,q,mxid,q).mxidx;
anss.pb(c[i] + (getans(1,0,q,q,q).sum - getans(1,0,q,leeid,leeid).sum));//<<endl;
}
}
return anss;
}
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:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int j = 0; j < v[i].size(); j++) {
| ~~^~~~~~~~~~~~~
candies.cpp:143:9: warning: unused variable 'mnval' [-Wunused-variable]
143 | int mnval = getans(1,0,q,ans,q).mn;
| ^~~~~
candies.cpp:145:9: warning: unused variable 'mxval' [-Wunused-variable]
145 | int mxval = getans(1,0,q,ans,q).mx;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7756 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7756 KB |
Output is correct |
| 5 |
Correct |
18 ms |
7752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2378 ms |
54052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
334 ms |
51240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
152 ms |
48404 KB |
Output is correct |
| 4 |
Correct |
841 ms |
13224 KB |
Output is correct |
| 5 |
Correct |
1903 ms |
54024 KB |
Output is correct |
| 6 |
Correct |
2130 ms |
54764 KB |
Output is correct |
| 7 |
Correct |
1989 ms |
55320 KB |
Output is correct |
| 8 |
Correct |
1864 ms |
54008 KB |
Output is correct |
| 9 |
Correct |
2008 ms |
55356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7372 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7756 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7756 KB |
Output is correct |
| 5 |
Correct |
18 ms |
7752 KB |
Output is correct |
| 6 |
Incorrect |
2378 ms |
54052 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
