oj.uz

Submission #437153

# Submission time Handle Problem Language Result Execution time Memory
437153 2021-06-25T23:33:04 Z pere_gil Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 12716 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Incorrect 4 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5080 ms 12716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Incorrect 4 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -