Submission #815187

#	Time	Username	Problem	Language	Result	Execution time	Memory
815187		I_Love_EliskaM_	Distributing Candies (IOI21_candies)	C++17	11 / 100	5026 ms	42120 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;

vector<int> p1(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size();
	vector<ll> a(n,0);
	forn(i,q) {
		for (int j=l[i]; j<=r[i]; ++j) {
			a[j]=min(a[j]+v[i],1ll*c[j]);
			a[j]=max(a[j],0ll);
		}
	}
	vector<int> ans(n);
	forn(i,n) ans[i]=a[i];
	return ans;
}

vector<int> p2(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size();
	vector<ll> pr(n+1);
	forn(i,q) {
		pr[l[i]]+=v[i];
		pr[r[i]+1]-=v[i];
	}
	forn(i,n) pr[i+1]+=pr[i];
	vector<int> ans(n);
	forn(i,n) ans[i]=min(pr[i],1ll*c[i]);
	return ans;
}

#define int long long
struct sgt {
	vector<int> lazy, mn, mx, type;
	int sz=1;
	sgt(int n) {
		while (sz<n) sz<<=1;
		lazy.assign(4*sz,0);
		mn=mx=type=lazy;
	}
	void fix(int v, int t, int x) {
		if (v>=2*sz-1) return;
		if (type[v]==0) {
			type[v]=t, lazy[v]=x; return;
		}
		if (type[v]==1) {
			if (t==1) {
				lazy[v]+=x; return;
			}
			push(v);
			//fix(2*v+1,type[v],lazy[v]);
			//fix(2*v+2,type[v],lazy[v]);
			type[v]=t;
			lazy[v]=x;
		} else if (type[v]==2) {
			if (t==2) {
				return;
			}
			push(v);
			//fix(2*v+1,type[v],lazy[v]);
			//fix(2*v+2,type[v],lazy[v]);
			type[v]=t;
			lazy[v]=x;
		} else {
			if (t==3) {
				return;
			}
			push(v);
			//fix(2*v+1,type[v],lazy[v]);
			//fix(2*v+2,type[v],lazy[v]);
			type[v]=t;
			lazy[v]=x;
		}
	}
	void push(int v) {
		if (v>=2*sz-1) return;
		if (type[v]==1) {
			mn[v]+=lazy[v];
			mx[v]+=lazy[v];
			fix(2*v+1,type[v],lazy[v]);
			fix(2*v+2,type[v],lazy[v]);
		} else if (type[v]==2) {
			mn[v]=max(mn[v],lazy[v]);
			mx[v]=max(mx[v],lazy[v]);
			fix(2*v+1,type[v],lazy[v]);
			fix(2*v+2,type[v],lazy[v]);
		} else {
			mn[v]=min(mn[v],lazy[v]);
			mx[v]=min(mx[v],lazy[v]);
			fix(2*v+1,type[v],lazy[v]);
			fix(2*v+2,type[v],lazy[v]);
		}
		type[v]=0;
		lazy[v]=0;
	}

	void add(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			type[v]=1; lazy[v]=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		add(2*v+1,l,m,lx,rx,x);
		add(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void add(int l, int r, int x) {
		add(0,0,sz,l,r,x);
	}

	void maxx(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			type[v]=2; lazy[v]=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		maxx(2*v+1,l,m,lx,rx,x);
		maxx(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void maxx(int l, int r, int x) {
		maxx(0,0,sz,l,r,x);
	}

	void minn(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			type[v]=3; lazy[v]=x;
			push(v);
			return;
		}
		int m=(l+r)>>1;
		minn(2*v+1,l,m,lx,rx,x);
		minn(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void minn(int l, int r, int x) {
		minn(0,0,sz,l,r,x);
	}

	void dfs(int v) {
		if (v>=2*sz-1) return;
		if (type[v]) push(v);
		dfs(2*v+1);
		dfs(2*v+2);
	}
};
#undef int

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size();
	if (max(n,q)<=2000) return p1(c,l,r,v);
	int z=1; forn(i,q) z&=v[i]>0;
	if (z) return p2(c,l,r,v);
	forn(i,n) if (c[i]!=c[0]) exit(0);

	#define int long long
	sgt st(n);
	forn(i,q) {
		st.add(l[i],r[i]+1,v[i]);
		if (v[i]>0) st.minn(l[i],r[i]+1,c[0]);
		else st.maxx(l[i],r[i]+1,0);
		//st.dfs(0);
		//forn(j,n) cout<<j<<": "<<st.mn[st.sz-1+j]<<' '<<st.mx[st.sz-1+j]<<'\n';
		//cout<<'\n';
	}
	st.dfs(0);
	vector<int32_t> ans;
	forn(i,n) assert(st.mn[st.sz-1+i]==st.mx[st.sz-1+i]);
	forn(i,n) ans.pb(st.mn[st.sz-1+i]);
	return ans;
	#undef int
}

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