| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1208120 | tkm_algorithms | 사탕 분배 (IOI21_candies) | C++20 | 0 ms | 0 KiB |
//#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=2*1e5+5;
struct upd
{
long long l,r,v,i;
upd(){}
upd(long long _l,long long _r,long long _v,long long _i)
{
l=_l;
r=_r;
v=_v;
i=_i;
}
bool operator<(const upd&u)const
{
return l<u.l;
}
};
struct segm
{
long long maxx,minn,maxi,mini,sum;
segm(){}
segm(long long x,long long n,long long xi,long long ni,long long s)
{
maxx=x;
minn=n;
maxi=xi;
mini=ni;
sum=s;
}
};
segm t[4*maxn];
long long lz[4*maxn];
void init(long long i,long long l,long long r)
{
lz[i]=0;
t[i].maxi=t[i].mini=l;
t[i].maxx=0;
t[i].minn=0;
t[i].sum=0;
if(l==r)
{
t[i].maxi=t[i].mini=l;
return;
}
long long m=(l+r)/2;
init(i*2,l,m);
init(i*2+1,m+1,r);
}
segm pull(segm s1,segm s2)
{
segm s={0,0,0,0,0};
if(s1.maxx>s2.maxx)
{
s.maxx=s1.maxx;
s.maxi=s1.maxi;
}
else
{
s.maxx=s2.maxx;
s.maxi=s2.maxi;
}
if(s1.minn<s2.minn)
{
s.minn=s1.minn;
s.mini=s1.mini;
}
else
{
s.minn=s2.minn;
s.mini=s2.mini;
}
s.sum=s1.sum+s2.sum;
return s;
}
void push(long long i,long long l,long long r)
{
t[i].minn+=lz[i];
t[i].maxx+=lz[i];
t[i].sum+=(r-l+1)*lz[i];
if(l!=r)
{
lz[i*2]+=lz[i];
lz[i*2+1]+=lz[i];
}
lz[i]=0;
}
void update(long long i,long long l,long long r,long long ql,long long qr,long long x)
{
push(i,l,r);
if(ql>qr)return;
if(ql<=l&&r<=qr)
{
lz[i]+=x;
push(i,l,r);
return;
}
long long m=(l+r)/2;
update(i*2,l,m,ql,min(qr,m),x);
update(i*2+1,m+1,r,max(m+1,ql),qr,x);
t[i]=pull(t[i*2],t[i*2+1]);
}
segm query(long long i,long long l,long long r,long long ql,long long qr)
{
push(i,l,r);
if(ql>qr)return {(long long)-1e18,(long long)1e18,0,0,0};
if(ql<=l&&r<=qr)return t[i];
long long m=(l+r)/2;
return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr));
}
upd u[maxn];
vector<upd> q[maxn];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
for(long long i=0;i<l.size();i++)
u[i]={l[i],r[i],v[i],i};
for(int i=0;i<c.size();i++)
q[i].clear();
sort(u,u+l.size());
vector<int> ans(c.size());
init(1,0,l.size()-1);
long long j=0;
long long sum=0;
for(long long i=0;i<c.size();i++)
{
while(j<l.size()&&u[j].l==i)
{
//cout<<"+ "<<u[j].i<<" "<<j<<endl;
sum+=u[j].v;
update(1,0,l.size()-1,u[j].i,l.size()-1,u[j].v);
q[u[j].r+1].push_back(u[j]);
j++;
}
for(long long j=0;j<q[i].size();j++)
{
//cout<<"- "<<q[i][j].i<<endl;
sum-=q[i][j].v;
update(1,0,l.size()-1,q[i][j].i,l.size()-1,-q[i][j].v);
}
long long wall=-1,tp=0;
long long lf=0,rt=l.size()-1;
long long stena = 0;
while(lf<=rt)
{
long long m=(lf+rt)/2;
segm s=query(1,0,l.size()-1,m,l.size()-1);
//cout<<m<<": "<<s.minn<<" "<<s.maxx<<" "<<s.mini<<" "<<s.maxi<<endl;
if(s.maxx-s.minn>=c[i])
{
//cout<<"in "<<endl;
//cout << s.maxx << " " << s.minn << endl;
if(s.maxi>s.mini) {
//cout << s.maxx << endl;
stena = s.maxx;
wall=s.maxi,tp=1;
}
else {
//cout << s.minn << endl;
stena = s.minn;
wall=s.mini,tp=0;
}
lf=m+1;
}
else rt=m-1;
}
//segm s = query(1, 0, l.size()-1, lf, l.size());
//cout << s.maxx << " " << s.minn << endl;
//cout<<sum<<endl;
//cout << << endl;
if(wall==-1)
{
wall=0;
segm s=query(1,0,l.size()-1,0,l.size()-1);
if(s.minn<0)wall=s.minn;
if(s.maxx>0&&s.maxx>=c[i]) {
//assert();
wall=s.maxx-c[i];
}
ans[i]=sum-wall;
continue;
}
//cout<<c[i]<<" > "<<wall<<endl;
//int onki =
//cout << wall << endl;
wall=query(1,0,l.size()-1,wall,wall).sum;
assert(stena == wall);
//cout << wall <<
if(tp==1)wall-=c[i];
ans[i]=sum-wall;
//cout<<i<<" "<<sum<<" "<<wall<<endl;
}
/*vector<int> ans2(c.size());
for(int i=0;i<l.size();i++)
{
for(int j=l[i];j<=r[i];j++)
{
ans2[j]+=v[i];
ans2[j]=max(0,ans2[j]);
ans2[j]=min(ans2[j],c[j]);
}
}
for(int i=0;i<c.size();i++)
if(ans[i]!=ans2[i])return {};*/
return ans;
}
void solve() {
int n, q;
cin >> n >> q;
vector<int> c(n), l(q), r(q), v(q);
for (auto &i : c) cin >> i;
for (auto &i : l) cin >> i;
for (auto &i : r) cin >> i;
for (auto &i : v) cin >> i;
vector<int> result = distribute_candies(c, l, r, v);
for (const auto &i : result) cout << i << " "; cout << '\n';
//int n;
//cin >> n;
//segtree T(n);
//while (1) {
//string op;
//int l, r, v;
//cin >> op;
//if (op == "add") {
//cin >> l >> v;
//T.add(l, v);
//}
//else if (op == "minimix") {
//cin >> l >> r;
//info res = T.minimix(l, r);
//printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
//}
//else if (op == "suffix") {
//cin >> v;
//info res = T.suffix(v);
//printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
//}
//}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
solve();
}