Submission #619734

#	Time	Username	Problem	Language	Result	Execution time	Memory
619734		nyaruhodo	Distributing Candies (IOI21_candies)	C++17	0 / 100	103 ms	48428 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> pr;

ll cap,n;
vi lazy;
vector<pr> seg; //min,max

void psh(ll v){
	lazy[v*2] += lazy[v],
	lazy[v*2+1] += lazy[v];
	seg[v*2].first += lazy[v];
	seg[v*2].second += lazy[v];
	seg[v*2+1].first += lazy[v];
	seg[v*2+1].second += lazy[v];
	lazy[v] = 0;
}

void correct(ll v,ll tl,ll tr){
	if(tl==tr){
		if(seg[v].first< 0) seg[v].first=0;
		if(seg[v].second>cap)seg[v].first=cap;
		return;
	}
	psh(v);
	ll tm=(tl+tr)/2;
	if(seg[v].first >= 0 && seg[v].second <= cap) return;
	if(seg[v].second < 0){
		seg[v].first+=-seg[v].second;
		seg[v].second=0;
		correct(v*2,tl,tm);
		correct(v*2+1,tm+1,tr);
	}	
	if(seg[v].first > cap){
		seg[v].second+= -seg[v].first;
		seg[v].first=cap;
		correct(v*2,tl,tm);
		correct(v*2+1,tm+1,tr);
	}	
}

void update(ll v,ll l,ll r,ll tl,ll tr,ll add){
	if(l > r) return;
	psh(v);
	if(tl==l && tr==r){
		seg[v].first +=add;
		seg[v].second+=add;
		lazy[v]+=add;
		return;
	}
	ll tm=(tl+tr)/2;
	update(v*2,l,min(r,tm),tl,tm,add);
	update(v*2+1,max(l,tm+1),r,tm+1,tr,add);
	seg[v].first = min(seg[v*2].first,seg[v*2+1].first);
	seg[v].second = max(seg[v*2].second,seg[v*2+1].second);
}

ll query(ll v,ll tl,ll tr,ll node){
	if(tl==tr) return seg[v].first;
	ll tm=(tl+tr)/2;
	psh(v);
	if(node<=tm) return query(v*2,tl,tm,node);
	else return query(v*2+1,tm+1,tr,node);
}

vector<int> distribute_candies(vector<int> c, 
vector<int> l, vector<int> r, vector<int> v){
	cap = c[0],n=c.size();
	seg.resize(4*n+100,{0,0}),lazy.resize(4*n+100,0);

	for(ll i = 0; i < l.size();i++){
		update(1,l[i]+1,r[i]+1,1,n,v[i]);
		correct(1,1,n);
	}

	vector<int> ret(n,0);
	for(ll i = 0; i < n;i++)
		ret[i] = query(1,1,n,i+1);
	return ret;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:75:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(ll i = 0; i < l.size();i++){
      |                ~~^~~~~~~~~~

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