Submission #437146

#	Time	Username	Problem	Language	Result	Execution time	Memory
437146		pere_gil	Distributing Candies (IOI21_candies)	C++17	0 / 100	5076 ms	12776 KiB

candies

#include "candies.h"
#include "bits/stdc++.h"
using namespace std;

#define index int med=(s+e)/2,l=2*n+1,r=2*n+2
#define vi vector<int> 
const int tam=2*1e5+5;

vi tr(4*tam,0),pen(4*tam,-1);

void lazy(int n, int s, int e, int val){
	pen[n]=-1;
	tr[n]+=(e-s+1)*val;

	if(s==e) return;

	index;
	if(pen[l]!=-1) lazy(l,s,med,pen[l]);
	if(pen[r]!=-1) lazy(r,med+1,e,pen[r]);
	pen[l]=pen[r]=val;
}

void update(int n, int s, int e, int i, int j, int val){
	if(pen[n]!=-1) lazy(n,s,e,pen[n]);
	if(i<=s && e<=j){
		lazy(n,s,e,val);
		return;
	}
	
	index;
	if(j<=med) update(l,s,med,i,j,val);
	else if(i>med) update(r,med+1,e,i,j,val);
	else update(l,s,med,i,j,val),update(r,med+1,e,i,j,val);
}

int query(int n, int s, int e, int i, int j){
	if(i<=s && e<=j){
		if(pen[n]!=-1) lazy(n,s,e,pen[n]);
		return tr[n];
	}

	index;
	if(j<=med) return query(l,s,med,i,j);
	if(i>med) return query(r,med+1,e,i,j);
	return query(l,s,med,i,j)+query(r,med+1,e,i,j);
}

vi distribute_candies(vi c, vi l, vi r, vi v){
	int n=c.size();
	int m=v.size();

	for(int i=0;i<m;i++)
		update(0,0,n-1,l[i],r[i],v[i]);
	
	vi ans(n,0);
	for(int i=0;i<n;i++)
		ans[i]=min(c[i],query(0,0,n-1,i,i));
	
	return ans;
}

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