Submission #625236

#	Time	Username	Problem	Language	Result	Execution time	Memory
625236		WongChun1234	Distributing Candies (IOI21_candies)	C++17	8 / 100	412 ms	30028 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200050;
struct node{
	ll sum,mn,mx;
}seg[N<<2];
node pushup(node a,node b){
	node ret;
	ret.sum=a.sum+b.sum;
	ret.mn=min(b.mn,a.mn+b.sum);
	ret.mx=max(b.mx,a.mx+b.sum);
	return ret;
}
vector<int> todo[N];
void build(int id,int l,int r){
	if (l==r){
		seg[id].sum=seg[id].mn=seg[id].mx=0;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
	seg[id]=pushup(seg[id*2],seg[id*2+1]);
}
void modify(int id,int l,int r,int q,int val){
	if (l>q||r<q) return;
	if (l==r){
		seg[id].sum+=val;
		seg[id].mn=min(0LL,seg[id].sum);
		seg[id].mx=max(0LL,seg[id].sum);
		return;
	}
	int mid=(l+r)/2;
	modify(id*2,l,mid,q,val); modify(id*2+1,mid+1,r,q,val);
	seg[id]=pushup(seg[id*2],seg[id*2+1]);
}
ll query(int id,int l,int r,int q,int c,ll cmin,ll cmax,ll curr){
	//if (l>q||r<q) return 0;
	if (l==r){
		//cout<<q<<":"<<l<<"::"<<curr<<","<<cmin<<"-"<<cmax<<"\n";
		ll tmax=max(cmax,curr+seg[id].sum),tmin=min(cmin,curr+seg[id].sum);
		//cout<<tmin<<"--"<<tmax<<"\n";
		if (tmax-tmin<=c) return seg[id].sum;
		if (seg[id].sum>=0){
			//hit r bound
			return -curr+cmin+c;
		}else{
			//hit l bound
			return cmax-curr;
		}
		//hit l or r
		/*+4 -1 +4
		0 to 7
		return l;*/
	}
	int mid=(l+r)/2;
	if (max(cmax,seg[id*2+1].mx+curr)-min(cmin,seg[id*2+1].mn+curr)<=c){
		return query(id*2,l,mid,q,c,min(cmin,seg[id*2+1].mn+curr),max(cmax,seg[id*2+1].mx+curr),curr+seg[id*2+1].sum)+seg[id*2+1].sum;
	}else{
		return query(id*2+1,mid+1,r,q,c,cmin,cmax,curr);
	}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size(), m = l.size();
	vector<int> s(n);
	for (int i=0;i<m;i++){
		todo[l[i]].push_back(i);
		todo[r[i]+1].push_back(i);
	}
	build(1,1,m);
	for (int i=0;i<n;i++){
		for (int j:todo[i]){
			if (l[j]==i){
				//add
				modify(1,1,m,j+1,v[j]);
			}else{
				//remove
				modify(1,1,m,j+1,-v[j]);
			}
		}
		s[i]=query(1,1,m,i+1,c[i],0,0,0);
	}
	return s;
}
/*
3
10 15 13
2
0 2 20
0 1 -11
*/
/*
3
10 15 13
3
0 2 4
1 2 5
0 1 10
*/

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