#include "candies.h"
#include<bits/stdc++.h>
#include <vector>
#define INF 1e18+7
using namespace std;
long long int n,m;
int a[2000005];
long long int capacity[2000005];
struct node
{
//tmx : tag maximum ; similar to define tmn , tad;
//cmx : the count of maximum; similar to define cmn; it is used to calculate the sum.
//mx2 : the second maximum;
long long int mx,mx2,mn,mn2,cmx,cmn,tmx,tmn,tad;
long long int sum;
}t[2000005];
void pushup(int u)
{
int lu = u * 2;int ru = u*2+1;
t[u].sum = t[lu].sum + t[ru].sum;
if(t[lu].mx == t[ru].mx)
{
t[u].mx = t[lu].mx;t[u].cmx = t[lu].cmx + t[ru].cmx;
t[u].mx2 = max(t[lu].mx2,t[ru].mx2);
}
if(t[lu].mx > t[ru].mx)
{
t[u].mx = t[lu].mx;t[u].cmx = t[lu].cmx;
t[u].mx2 = max(t[lu].mx2,t[ru].mx);
}
if(t[lu].mx < t[ru].mx)
{
t[u].mx = t[ru].mx;t[u].cmx = t[ru].cmx;
t[u].mx2 = max(t[ru].mx2,t[lu].mx);
}
if(t[lu].mn == t[ru].mn)
{
t[u].mn = t[lu].mn;t[u].cmn = t[lu].cmn + t[ru].cmn;
t[u].mn2 = min(t[lu].mn2,t[ru].mn2);
}
if(t[lu].mn < t[ru].mn)
{
t[u].mn = t[lu].mn;t[u].cmn = t[lu].cmn;
t[u].mn2 = min(t[lu].mn2,t[ru].mn);
}
if(t[lu].mn > t[ru].mn)
{
t[u].mn = t[ru].mn;t[u].cmn = t[ru].cmn;
t[u].mn2 = min(t[ru].mn2,t[lu].mn);
}
return;
}
void push_add(int nownode,long long int l,long long int r,long long int v)
{
// this function is for update the value of nownode[l,r];
t[nownode].sum += (long long)((r-l+1)) * v;
t[nownode].mx += v;t[nownode].mn += v;
if(t[nownode].mx2 != -INF)t[nownode].mx2 += v;
if(t[nownode].mn2 != INF)t[nownode].mn2 += v;
if(t[nownode].tmx != -INF)t[nownode].tmx += v;
if(t[nownode].tmn != INF)t[nownode].tmn += v;
t[nownode].tad += v;
return;
}
void push_min(int nownode, long long int tag)
{
//we should do the following things: if nownode.mx <= tag , return; otherwise update it .
// this function is for update the tmn of nownode.
if(t[nownode].mx <= tag)return;
t[nownode].sum += (long long)(tag - t[nownode].mx) * t[nownode].cmx;
if(t[nownode].mn2 == t[nownode].mx)t[nownode].mn2 = tag;
if(t[nownode].mn == t[nownode].mx)t[nownode].mn = tag;
if(t[nownode].tmx > tag)t[nownode].tmx = tag;
t[nownode].mx = tag;t[nownode].tmn = tag;
return;
}
void push_max(int nownode,long long int tag)
{
if(t[nownode].mn > tag)return;
t[nownode].sum += (long long)(tag-t[nownode].mn) * t[nownode].cmn;
if(t[nownode].mx2 == t[nownode].mn)t[nownode].mx2 = tag;
if(t[nownode].mx == t[nownode].mn)t[nownode].mx = tag;
if(t[nownode].tmn < tag)t[nownode].tmn = tag;
t[nownode].mn = tag;t[nownode].tmx = tag;
return;
}
void pushdown(int u,int l,int r)
{
int lu = u*2;int ru = u*2+1;int mid = (l+r)>>1;
if(t[u].tad != 0)
{
push_add(lu,l,mid,t[u].tad);
push_add(ru,mid+1,r,t[u].tad);
}
if(t[u].tmx != -INF)push_max(lu,t[u].tmx),push_max(ru,t[u].tmx);
if(t[u].tmn != INF)push_min(lu,t[u].tmn),push_min(ru,t[u].tmn);
t[u].tad = 0;t[u].tmx = -INF;t[u].tmn = INF;
return;
}
void build(int nownode,int l,int r)
{
t[nownode].tmn = INF; t[nownode].tmx = -INF;
if(l == r)
{
t[nownode].sum = t[nownode].mx = t[nownode].mn = a[l];
t[nownode].mx2 = -INF;t[nownode].mn2 = INF;
t[nownode].cmx = t[nownode].cmn = 1;
return;
}
int mid = (l+r)>>1;
build(nownode*2 ,l,mid);build(nownode*2+1, mid+1 , r);
pushup(nownode);
return;
}
void add(int L,int R,int v,int u,int l,int r)
{
// l -> nowl , r -> nowr;
if(R < l || r < L)return;
if(L <= l && r <= R)
{
push_add(u,l,r,v);return;
}
int mid = (l+r)>>1;
pushdown(u,l,r);
add(L,R,v,u*2,l,mid);
add(L,R,v,u*2+1,mid+1,r);
pushup(u);
return;
}
long long int qsum(int L,int R,int u,int l,int r)
{
if(R < l || r < L)return 0;
if(L <= l && r <= R)return t[u].sum;
int mid = (l+r)>>1;
pushdown(u,l,r);
long long int ans = 0;
ans += (qsum(L,R,u*2,l,mid) + qsum(L,R,u*2+1,mid+1,r));
return ans;
}
void tomin(int L,int R,int v,int u,int l,int r)
{
//there are 3 situation for getting minimum:
//first , if nownode.mx <= v, it is no use for this operation,return;
//second, if second max < t <= max , we can operate this node directly.
//last , if t <= second max , we don't know how many number, we need recursion more.
if(R < l || r < L || t[u].mx <= v)return;
if(L <= l && r <= R && t[u].mx2 < v)
{
push_min(u,v);
return;
}
int mid = (l+r)>>1;
pushdown(u,l,r);
tomin(L,R,v,u*2,l,mid);
tomin(L,R,v,u*2+1,mid+1,r);
pushup(u);
return;
}
void tomax(int L,int R,int v,int u,int l,int r)
{
if(R < l || r < L || t[u].mn >= v)return;
if(L <= l && r <= R && t[u].mn2 > v)
{
push_max(u,v);
return;
}
int mid = (l+r)>>1;
pushdown(u,l,r);
tomax(L,R,v,u*2,l,mid);
tomax(L,R,v,u*2+1,mid+1,r);
pushup(u);
return;
}
vector<int> rpp;
vector<int> distribute_candies(vector<int> c,vector<int> ll,vector<int> rr,vector<int> vv)
{
n = c.size();
if(n <= 2000 && ll.size() <= 2000)
{
for(int i=0;i<=n-1;i++)a[i] = 0;
for(int i=0;i<ll.size();i++)
{
int xx = ll[i];
int yy = rr[i];
for(int j=xx;j<=yy;j++)
{
a[j] += vv[i];
a[j] = min(c[j],a[j]);
a[j] = max(0,a[j]);
}
}
for(int i=0;i<n;i++)
{
rpp.push_back(a[i]);
}
return rpp;
}
int k = c[0];
for(int i=1;i<=n;i++)a[i] = 0;
build(1,1,n);
for(int i=0;i<ll.size();i++)
{
ll[i] += 1;rr[i] += 1;
}
for(int i=0;i<ll.size();i++)
{
add(ll[i],rr[i],vv[i],1,1,n);
tomin(1,n,k,1,1,n);
tomax(1,n,0,1,1,n);
}
for(int i=1;i<=n;i++)
{
long long int xx = qsum(i,i,1,1,n);
rpp.push_back(xx);
}
return rpp;
}
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:182:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for(int i=0;i<ll.size();i++)
| ~^~~~~~~~~~
candies.cpp:202:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | for(int i=0;i<ll.size();i++)
| ~^~~~~~~~~~
candies.cpp:206:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int i=0;i<ll.size();i++)
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2408 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
671 ms |
53680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
183 ms |
9432 KB |
Output is correct |
| 3 |
Correct |
91 ms |
50100 KB |
Output is correct |
| 4 |
Correct |
483 ms |
53620 KB |
Output is correct |
| 5 |
Correct |
700 ms |
53704 KB |
Output is correct |
| 6 |
Correct |
923 ms |
53864 KB |
Output is correct |
| 7 |
Correct |
785 ms |
53680 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
45 ms |
12012 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2408 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 6 |
Incorrect |
671 ms |
53680 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
