#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=201000;
int n,q;
VI qs2[N];
vector<PII> qs[N];
ll pref4[N],mn[N],mx[N];
struct node{
ll valfg,val,mn,mx;
node() {mn=mx=val=valfg=0;}
}nd[4*N];
void upd(int p) {
nd[p].mn=min(nd[p*2].mn,nd[p*2+1].mn);
nd[p].mx=max(nd[p*2].mx,nd[p*2+1].mx);
}
void push(int p) {
nd[p].val+=nd[p].valfg;
// nd[p].mn=min(nd[p].mn,nd[p].mn+nd[p].valfg);
// nd[p].mx=max(nd[p].mx,nd[p].mx+nd[p].valfg);
nd[p].mn+=nd[p].valfg;
nd[p].mx+=nd[p].valfg;
nd[p*2].valfg+=nd[p].valfg;
nd[p*2+1].valfg+=nd[p].valfg;
nd[p].valfg=0;
}
//void updval(int p,int l,int r,int tl,int tr,int x) {
// if (l>r||l>tr||r<tl) return;
// if (tl<=l&&r<=tr) {
// nd[p].valfg+=x;
// push(p);
// return;
// }
// push(p);
// int md=(l+r)>>1;
// updval(p*2,l,md,tl,tr,x);
// updval(p*2+1,md+1,r,tl,tr,x);
// upd(p);
//}
ll getmn(int p,int l,int r,int tl,int tr) {
push(p);
if (l>tr||r<tl) return 1e18;
if (tl<=l&&r<=tr) return nd[p].mn;
int md=(l+r)>>1;
ll L=getmn(p*2,l,md,tl,tr);
ll R=getmn(p*2+1,md+1,r,tl,tr);
upd(p);
return min(L,R);
}
ll getmx(int p,int l,int r,int tl,int tr) {
push(p);
if (l>tr||r<tl) return -1e18;
if (tl<=l&&r<=tr) return nd[p].mx;
int md=(l+r)>>1;
ll L=getmx(p*2,l,md,tl,tr);
ll R=getmx(p*2+1,md+1,r,tl,tr);
upd(p);
return max(L,R);
}
ll getval(int p,int l,int r,int x) {
push(p);
if (l==r) return nd[p].val;
int md=(l+r)>>1;
if (x<=md) return nd[p].valfg+getval(p*2,l,md,x);
else return nd[p].valfg+getval(p*2+1,md+1,r,x);
}
void modify(int p,int l,int r,int tl,int tr,int x) {
push(p);
if (l>tr||r<tl) return;
if (tl<=l&&r<=tr) {
nd[p].valfg+=x;
push(p);
return;
}
push(p);
int md=(l+r)>>1;
modify(p*2,l,md,tl,tr,x);
modify(p*2+1,md+1,r,tl,tr,x);
upd(p);
}
VI distribute_candies(VI c,VI l,VI r,VI v) {
n=SZ(c),q=SZ(v);
VI a(n);
// if (n<=2000&&q<=2000&&false) {
// rep(i,0,q) rep(j,l[i],r[i]+1) a[j]+=v[i],a[j]=max(a[j],0),a[j]=min(a[j],c[j]);
// return a;
// }
// bool sb2=true;
// rep(i,0,q) if (v[i]<0) sb2=false;
// if (sb2&&false) {
// rep(i,0,q) {
// qs2[l[i]].pb(v[i]);
// qs2[r[i]+1].pb(-v[i]);
// }
// ll tot=0;
// rep(i,0,n) {
// for (auto x:qs2[i]) tot+=x;
// a[i]=min((ll)c[i],tot);
// }
// return a;
// }
bool sb4=true;
rep(i,0,q) if (l[i]!=0||r[i]!=n-1) sb4=false;
if (sb4&&false) {
printf("gas\n");
pref4[0]=v[0];
rep(i,1,q) pref4[i]=pref4[i-1]+v[i];
mx[q-1]=mn[q-1]=pref4[q-1];
per(i,0,q-1) mx[i]=max(pref4[i],mx[i+1]),mn[i]=min(pref4[i],mn[i+1]);
rep(i,0,n) {
// for (auto x:qs[i]) {
// int id=x.fi;
// int val=x.se;
// updval(1,0,q-1,id,q-1,val);
// }
if (mx[0]-mn[0]<=c[i]) a[i]=pref4[q-1]-mn[0];
else {
int l=0,r=q-1,pos=0;
while (l<=r) {
int md=(l+r)>>1;
if (mx[md]-mn[md]>c[i]) pos=md,l=md+1;
else r=md-1;
}
if (pref4[pos]<pref4[q-1]) a[i]=c[i]-(mx[pos]-pref4[q-1]);
else a[i]=pref4[q-1]-mn[pos];
}
}
return a;
}
rep(i,0,q) {
qs[l[i]].pb(mp(i+1,v[i]));
qs[r[i]+1].pb(mp(i+1,-v[i]));
}
rep(i,0,n) {
for (auto x:qs[i]) modify(1,0,q,x.fi,q-1,x.se);
if (getmx(1,0,q,0,q)-getmn(1,0,q,0,q)<=c[i]) a[i]=getval(1,0,q,q)-getmn(1,0,q,0,q);
else {
int l=1,r=q,pos=0;
while (l<=r) {
int md=(l+r)>>1;
if (getmx(1,0,q,md,q)-getmn(1,0,q,md,q)>c[i]) pos=md,l=md+1;
else r=md-1;
}
// printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
if (getval(1,0,q,pos)<getval(1,0,q,q)) a[i]=c[i]-(getmx(1,0,q,pos,q)-getval(1,0,q,q));
else a[i]=getval(1,0,q,q)-getmn(1,0,q,pos,q);
// rep(j,0,q) printf("%d ",getval(1,0,q-1,j)); puts("");
}
}
return a;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
34892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
433 ms |
108732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
34896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
34860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
34892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
