Submission #1052937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052937		tolbi	Distributing Candies (IOI21_candies)	C++17	11 / 100	118 ms	14676 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tol(bi) ((1LL)<<((int)(bi)))
struct DumduzSegTree{
	vector<int> segtree;
	DumduzSegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
	}
	void update(int tl, int tr, int v, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tl && r<=tr) return void(segtree[node]+=v);
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl, tr, v, l, mid, node*2+1);
		if (mid<tr) update(tl, tr, v, mid+1, r, node*2+2);
	}
	int query(int x){
		int l = 0, r = segtree.size()/2, node = 0;
		int ret = 0;
		while (l<r){
			ret+=segtree[node];
			int mid = l+(r-l)/2;
			if (x<=mid){
				r=mid;
				node=node*2+1;
			}
			else {
				l=mid+1;
				node=node*2+2;
			}
		}
		return ret+segtree[node];
	}
};
template<typename T> vector<int32_t> normalize(vector<T> v){
	vector<int32_t> ret(v.size());
	for (int i = 0; i < v.size(); ++i)
	{
		ret[i]=v[i];
	}
	return ret;
}
struct HafifDegisikSegTree{
	vector<int> segtree;
	int k;
	HafifDegisikSegTree(int n, int k):k(k){
		segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
	};
	void dallan(int node){
		if (node*2+1<segtree.size()){
			segtree[node*2+1]+=segtree[node];
			segtree[node*2+2]+=segtree[node];
			segtree[node*2+1]=max(0ll,min(k,segtree[node*2+1]));
			segtree[node*2+2]=max(0ll,min(k,segtree[node*2+2]));
			segtree[node]=0;
		}
	}
	void update(int tl, int tr, int v, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tl && r<=tr) return segtree[node]+=v,dallan(node);
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl, tr, v, l, mid, node*2+1);
		if (mid<tr) update(tl,tr,v,mid+1,r,node*2+2);
	}
	int query(int x){
		int l = 0, r = segtree.size(), node = 0;
		while (l<r){
			int mid = l+(r-l)/2;
			dallan(node);
			node=node*2+1;
			if (x<=mid){
				r=mid;
			}
			else {
				l=mid+1;
				node++;
			}
		}
		return segtree[node];
	}
};
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
	int n = c.size(), q = l.size();
	bool sub2 = true;
	bool sub3 = true;
	for (int i = 0; i < q; i++){
		if (v[i]<0) sub2=false;
	}
	for (int i = 0; i < n; ++i)
	{
		if (c[i]!=c[0]) sub3=false;
	}
	if (n<=2000 && q<=2000){
		vector<int> ret(n);
		for (int i = 0; i < q; ++i)
		{
			for (int j = l[i]; j <= r[i]; j++){
				ret[j]=max(0ll,min((int)c[j],ret[j]+v[i]));
			}
		}
		return normalize(ret);
	}
	else if (sub2){
		DumduzSegTree segtree(n);
		for (int i = 0; i < q; i++){
			segtree.update(l[i],r[i],v[i]);
		}
		vector<int> ret(n);
		for (int i = 0; i < n; i++){
			ret[i]=min((int)c[i],segtree.query(i));
		}
		return normalize(ret);
	}
	else if (sub3){
		HafifDegisikSegTree segtree(n,c[0]);
		for (int i = 0; i < n; ++i)
		{
			segtree.update(l[i],r[i],v[i]);
		}
		vector<int> ret(n);
		for (int i = 0; i < n; ++i)
		{
			ret[i]=segtree.query(i);
		}
		return normalize(ret);
	}
	else {
		//subtask4
		return normalize(vector<int>(n,23));
	}
}

Compilation message (stderr)

candies.cpp: In member function 'void HafifDegisikSegTree::dallan(long long int)':
candies.cpp:52:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if (node*2+1<segtree.size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~
candies.cpp: In instantiation of 'std::vector<int> normalize(std::vector<_Tp>) [with T = long long int]':
candies.cpp:105:23:   required from here
candies.cpp:39:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < v.size(); ++i)
      |                  ~~^~~~~~~~~~

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