Submission #917251

#	Time	Username	Problem	Language	Result	Execution time	Memory
917251		jamjanek	Distributing Candies (IOI21_candies)	C++17	100 / 100	717 ms	33720 KiB

candies

#include<bits/stdc++.h>
using namespace std;

long long c[200010];

struct node{long long mini, maxi, lazy;};
const int base = 1<<18;
node tree[2*base];

void push(int w){
	if(w>=base)return;
	tree[w*2].lazy+=tree[w].lazy;
	tree[w*2+1].lazy+=tree[w].lazy;
	tree[w*2].mini+=tree[w].lazy;
	tree[w*2].maxi+=tree[w].lazy;
	tree[w*2+1].mini+=tree[w].lazy;
	tree[w*2+1].maxi+=tree[w].lazy;
	tree[w].lazy = 0;
}

void update(int w, int l, int p, int a, int b, long long val){
	push(w);
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		tree[w].lazy+=val;
		tree[w].maxi+=val;
		tree[w].mini+=val;
		return;
	}
	update(w*2, l, (l+p)/2, a, b, val);
	update(w*2+1, (l+p)/2+1, p, a, b, val);
	tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
	tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}

long long maxi(int w, int l, int p, int a, int b){
	push(w);
	if(l>b || p<a)return -1000000000000000000;
	if(a<=l && p<=b){
		return tree[w].maxi;
	}
	return max(maxi(w*2, l, (l+p)/2, a, b), maxi(w*2+1, (l+p)/2+1, p, a, b));
//	tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
//	tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}


long long mini(int w, int l, int p, int a, int b){
	push(w);
	if(l>b || p<a)return 1000000000000000000;
	if(a<=l && p<=b){
		return tree[w].mini;
	}
	return min(mini(w*2, l, (l+p)/2, a, b), mini(w*2+1, (l+p)/2+1, p, a, b));
//	tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
//	tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}


vector<int> distribute_candies(vector<int>C, vector<int>l, vector<int>r, vector<int> V)
{
    vector<int>ans;
	int n, q, i, a, b, v;
	n = C.size();
	for(i=0;i<n;i++)
		c[i] = C[i];
	q = l.size();
	vector<pair<int,pair<int,int>>>sorted;
	for(i=1;i<=q;i++){
	    a = l[i-1];
	    b = r[i-1];
	    v = V[i-1];
		scanf("%d%d%d", &a, &b, &v);
		sorted.push_back({a, {i, v}});
		sorted.push_back({b+1, {i, -v}});
	}
	for(i=q+1;i<base;i++){
		tree[base+i].mini = 1000000000000000000;
		tree[base+i].maxi = -1000000000000000000;
	}
	for(i=base-1;i>0;i--){
		tree[i].maxi = max(tree[i*2].maxi, tree[i*2+1].maxi);
		tree[i].mini = min(tree[i*2].mini, tree[i*2+1].mini);
	}
	sort(sorted.begin(), sorted.end());
	int it = 0;
	for(i=0;i<n;i++){
		while(it<(int)sorted.size() && sorted[it].first==i){
			update(1, 0, base-1, sorted[it].second.first, q, sorted[it].second.second);
			it++;
		}
		int p;
		if(tree[1].maxi-tree[1].mini>=c[i]){
			int w = 1;
			long long sufMAX = -1000000000000000000, sufMIN = 1000000000000000000;
			while(w<base){
				push(w);
				if(max(sufMAX, tree[w*2+1].maxi)-min(sufMIN, tree[w*2+1].mini)>=c[i])
					w = w*2+1;
				else{
					sufMAX = max(sufMAX, tree[w*2+1].maxi);
					sufMIN = min(sufMIN, tree[w*2+1].mini);
					w = w*2;
				}
			}
			p = w-base;
		}
		else{
			p = -1;
		}

		if(p==-1)
			ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, 0, q));
		else{
			if(mini(1, 0, base-1, p, q)==mini(1, 0, base-1, p, p))
				ans.push_back(mini(1, 0, base-1, q, q)-maxi(1, 0, base-1, p, q)+c[i]);
			else
				ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, p, q));
		}
	}
	return ans;
}

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:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d%d", &a, &b, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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