Submission #437153

#	Time	Username	Problem	Language	Result	Execution time	Memory
437153		pere_gil	Distributing Candies (IOI21_candies)	C++17	0 / 100	5080 ms	12716 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 pri(int n, int s, int e){
	printf("[%d ; %d] = %d || ",s,e,tr[n]);
	(pen[n]==-1) ? printf("none\n") : printf("%d\n",pen[n]);
	index;
	if(s==e) return;
	pri(l,s,med);
	pri(r,med+1,e);
}

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){
		pen[n]=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]);
		//printf("update in [%d ; %d]\n",l[i],r[i]);
		//pri(0,0,n-1);
		//printf("\n");
	}
	
	vi ans(n,0);
	for(int i=0;i<n;i++){
		ans[i]=min(c[i],query(0,0,n-1,i,i));
		//printf("query in [%d ; %d]\n",i,i);
		//pri(0,0,n-1);
		//printf("\n");
	}
	return ans;
}

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