//by szh
#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 200010;
int n,m;
int hi[maxn];
pii hii[maxn];
vector <int> ans;
vector <ll> anss;
struct Q{
int l,r,v;
}q[maxn];
vector <int> solve1() {
rep(i,0,n) ans.pb(0);
rep(i,0,m) {
rep(j,q[i].l,q[i].r+1) {
ans[j] += q[i].v;
if (ans[j]<0) ans[j]=0;
if (ans[j]>hi[j]) ans[j] = hi[j];
}
}
return ans;
}
vector <int> solve2(){
rep(i,0,n) anss.pb(0);
rep(i,0,m) {
anss[q[i].l]+=q[i].v;
if (q[i].r+1<SZ(anss))anss[q[i].r+1]-=q[i].v;
}
rep(i,1,n) anss[i] += anss[i-1];
rep(i,0,n) {
if (anss[i]>hi[i]) ans.pb(hi[i]);
else ans.pb(anss[i]);
}
return ans;
}
vector <int> solve3() {
return ans;
}
pii tree[maxn*4];
pii add[maxn*4];
void init(int c,int cl,int cr) {
if (cl==cr) {
tree[c]={1,0};
add[c]={0,0};
}
else {
int mid=cl+cr>>1;
init(c<<1,cl,mid);
init(c<<1|1,mid+1,cr);
}
}
void push_down(int c) {
if (add[c].fi!=0) {
tree[c<<1] = tree[c<<1|1] = add[c<<1] = add[c<<1|1] = add[c];
}
else {
tree[c<<1].se += add[c].se;
tree[c<<1|1].se += add[c].se;
add[c<<1].se += add[c].se;
add[c<<1|1].se += add[c].se;
}
add[c] = {0,0};
}
void update(int c,int cl,int cr,int l,int r,int type,int val) {
if (l<=cl and cr<=r) {
if (type==0) {
tree[c].se += val;
add[c].se += val;
}
else if (type==1) {
tree[c] = {1,0};
add[c] = {1,0};
}
else tree[c] = {2,0},add[c] = {2,0};
return;
}
push_down(c);
int mid = cl+cr>>1;
if (l<=mid) update(c<<1,cl,mid,l,r,type,val);
if (r>mid) update(c<<1|1,mid+1,cr,l,r,type,val);
return;
}
pii query(int c,int cl,int cr,int pos) {
if (cl==cr) return tree[c];
push_down(c);
int mid=cl+cr>>1;
if (pos<=mid) return query(c<<1,cl,mid,pos);
else return query(c<<1|1,mid+1,cr,pos);
}
int query(int pos) {
pii tmp = query(1,0,n-1,pos);
if (tmp.fi==1) return tmp.se;
else return hii[pos].fi+tmp.se;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n = SZ(c),m = SZ(l);
rep(i,0,n) hi[i] = c[i],hii[i] = {c[i],i};
rep(i,0,m) q[i].l = l[i],q[i].r = r[i], q[i].v = v[i];
if (n<=2000) return solve1();
bool check=true;
rep(i,1,n) if (c[i]!=c[i-1]) check=false;
if (check) return solve3();
check=true;
rep(i,0,m) if (v[i]<=0) check=false;
if (check) return solve2();
//subtask 4
init(1,0,n-1);
rep(i,0,n) ans.pb(0);
sort(hii,hii+n);
rep(i,0,m) {
int cur = q[i].v;
if (cur==0) continue;
if (cur<0) {
int l = -1,r=n-1;
while (l<r) {
int mid=l+r+1>>1;
if (mid==-1 or query(mid)+cur<0) l=mid;
else r = mid-1;
}
if (l>=0) update(1,0,n-1,0,l,1,0);
if (l+1<n) update(1,0,n-1,l+1,n-1,0,cur);
}
else {
int l = -1,r=n-1;
while (l<r) {
int mid=l+r+1>>1;
if (mid==-1 or query(mid)+cur>hii[mid].fi) l=mid;
else r = mid-1;
}
if (l>=0) update(1,0,n-1,0,l,1,0);
if (l+1<n) update(1,0,n-1,l+1,n-1,0,cur);
}
// debug(query(0));debug(query(2));
}
rep(i,0,n) ans[hii[i].se]=(query(i));
return ans;
}
Compilation message
candies.cpp: In function 'void init(int, int, int)':
candies.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid=cl+cr>>1;
| ~~^~~
candies.cpp: In function 'void update(int, int, int, int, int, int, int)':
candies.cpp:109:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int mid = cl+cr>>1;
| ~~^~~
candies.cpp: In function 'std::pair<int, int> query(int, int, int, int)':
candies.cpp:118:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
118 | int mid=cl+cr>>1;
| ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:152:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
152 | int mid=l+r+1>>1;
| ~~~^~
candies.cpp:162:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
162 | int mid=l+r+1>>1;
| ~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
6 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
15176 KB |
Output is correct |
| 2 |
Correct |
106 ms |
15308 KB |
Output is correct |
| 3 |
Correct |
103 ms |
15392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
455 ms |
8196 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
4996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1290 ms |
8196 KB |
Output is correct |
| 4 |
Incorrect |
92 ms |
15236 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
6 ms |
492 KB |
Output is correct |
| 6 |
Correct |
106 ms |
15176 KB |
Output is correct |
| 7 |
Correct |
106 ms |
15308 KB |
Output is correct |
| 8 |
Correct |
103 ms |
15392 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
455 ms |
8196 KB |
Output is correct |
| 11 |
Incorrect |
25 ms |
4996 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
