Submission #1302676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302676		vtnoo	Distributing Candies (IOI21_candies)	C++20	0 / 100	168 ms	13616 KiB

candies

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
struct Nodo{
	int mn=0,mx=0,lz=0;
};
Nodo st[MAXN*4];
int n,lim;
void apply(int v,int x){
	st[v].mn+=x;
	st[v].mx+=x;
	st[v].lz+=x;
}
void push(int v){
	apply(v*2,st[v].lz);
	apply(v*2+1,st[v].lz);
	st[v].lz=0;
}
void upd(int ts,int te,int x,int v=1,int s=0,int e=n-1){
	if(e<ts||te<s)return;
	if(ts<=s&&e<=te){
		apply(v,x);
		return;
	}else{
		push(v);
		int m=(s+e)/2;
		upd(ts,te,x,v*2,s,m);
		upd(ts,te,x,v*2+1,m+1,e);
		st[v].mn=min(st[v*2].mn,st[v*2+1].mn);
		st[v].mx=max(st[v*2].mx,st[v*2+1].mx);
	}
}
void fix_floor(int ts,int te,int v=1,int s=0,int e=n-1){
	if(st[v].mn>=0){
		return;
	}
	if(st[v].mx<0){
		apply(v,-st[v].mx);
	}
	if(s==e)return;
	push(v);
	if(st[v].mn<0&&st[v].mx>=0){
		int m=(s+e)/2;
		fix_floor(ts,te,v*2,s,m);
		fix_floor(ts,te,v*2+1,m+1,e);
		st[v].mn=min(st[v*2].mn,st[v*2+1].mn);
		st[v].mx=max(st[v*2].mx,st[v*2+1].mx);
	}
}
void fix_ceil(int ts,int te,int v=1,int s=0,int e=n-1){
	if(st[v].mx<=lim){
		return;
	}
	if(st[v].mn>lim){
		apply(v,lim-st[v].mn);
	}
	if(s==e)return;
	push(v);
	if(st[v].mn<0&&st[v].mx>=0){
		int m=(s+e)/2;
		fix_ceil(ts,te,v*2,s,m);
		fix_ceil(ts,te,v*2+1,m+1,e);
		st[v].mn=min(st[v*2].mn,st[v*2+1].mn);
		st[v].mx=max(st[v*2].mx,st[v*2+1].mx);
	}
}
int get(int pos,int v=1,int s=0,int e=n-1){
	if(s==e){
		return st[v].mn;
	}
	push(v);
	int m=(s+e)/2;
	if(pos<=m)return get(pos,v*2,s,m);
	else return get(pos,v*2+1,m+1,e);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=SZ(c);
    int q=SZ(l);
    lim=c[0];
    fore(i,0,q){
		upd(l[i],r[i],v[i]);
		fix_floor(0,n-1);
		fix_ceil(0,n-1);
	}
	vector<int>ret(n);
	fore(i,0,n){
		ret[i]=get(i);
	}
	return ret;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33