#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second
ll n, m, q;
pll d[1000001];
ll tt[1000001];
void build(int h,int l,int r)
{
if (l==r)
{
d[h]=mp(0, 0);
return;
}
int w=(l+r)/2;
build(h*2,l,w);
build(h*2+1,w+1,r);
d[h]=mp(0, 0);
}
void push(int h)
{
if (tt[h])
{
d[h*2].fi+=tt[h];
d[h*2].se+=tt[h];
d[h*2+1].fi+=tt[h];
d[h*2+1].se+=tt[h];
tt[h*2]+=tt[h];
tt[h*2+1]+=tt[h];
}
}
void update(int h,int l,int r,int x,int y,int k)
{
if (x>y) return;
if (l==x && y==r)
{
d[h].fi+=k;
d[h].se+=k;
tt[h]+=k;
return;
}
push(h);
int w=(l+r)/2;
update(h*2,l,w,x,min(y,w),k);
update(h*2+1,w+1,r,max(x,w+1),y,k);
d[h].fi=min(d[h*2].fi,d[h*2+1].fi);
d[h].se=max(d[h*2].se,d[h*2+1].se);
}
ll get_min(int h,int l,int r,int x,int y)
{
if (x>y) return 1e18;
if (l==x && y==r) return d[h].fi;
int w=(l+r)/2;
push(h);
return min(get_min(h*2,l,w,x,min(y,w)), get_min(h*2+1,w+1,r,max(x,w+1),y));
}
ll get_max(int h,int l,int r,int x,int y)
{
if (x>y) return -1e18;
if (l==x && y==r) return d[h].se;
int w=(l+r)/2;
push(h);
return max(get_max(h*2,l,w,x,min(y,w)), get_max(h*2+1,w+1,r,max(x,w+1),y));
}
ll get(int h,int l,int r,int x)
{
if (l==r)
{
return d[h].fi;
}
int w=(l+r)/2;
if (x<=w) return get(h*2,l,w,x); else return get(h*2+1,w+1,r,x);
}
vector<pll> gg[1000001];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n=c.size();
q=l.size();
for (int i = 0; i < q; i++)
{
gg[l[i]].pb(mp(i, v[i]));
gg[r[i]+1].pb(mp(i, -v[i]));
}
vector<int> ans;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < gg[i].size(); j++)
{
update(1,0,q,gg[i][j].fi+1,q,gg[i][j].se);
}
//cout << i << " " << d[1].fi << " " << d[1].se << "\n";
if (d[1].se-d[1].fi<c[i])
{
ans.pb(get(1,0,q,q)-get_min(1,0,q,0,q));
continue;
}
ll l=0, r=q;
while (l<r)
{
int w=(l+r+1)/2;
if (get_max(1,0,q,w,q)-get_min(1,0,q,w,q)>=c[i]) l=w; else r=w-1;
}
ll o1=get(1,0,q,l), o2=get(1,0,q,q);
if (o1<o2)
{
ll o3=get_max(1,0,q,l+1,q);
ans.pb(c[i]-(o3-o2));
}else
{
ll o3=get_min(1,0,q,l+1,q);
ans.pb(o2-o3);
}
}
return ans;
}
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:109:27: 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]
109 | for (int j = 0; j < gg[i].size(); j++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
599 ms |
53948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
