oj.uz

Submission #437146

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

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 6572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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