Submission #597763

#	Time	Username	Problem	Language	Result	Execution time	Memory
597763		idiot123	Distributing Candies (IOI21_candies)	C++17	100 / 100	630 ms	42948 KiB

candies

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

using namespace std;

const long long INF = 1e18;

class Tree{
	private:
	int lrSize = 2;
	vector<long long> maxVal;
	vector<long long> minVal;
	vector<long long> lazy;
	
	void update(int pos, bool up){
		minVal[pos] = min(minVal[2*pos], minVal[2*pos+1]);
		maxVal[pos] = max(maxVal[2*pos], maxVal[2*pos+1]);
		if(pos > 1 && up)update(pos/2, true);
	}
	
	void push(int pos){
		minVal[2*pos] += lazy[pos];
		maxVal[2*pos] += lazy[pos];
		lazy[2*pos] += lazy[pos];
		minVal[2*pos + 1] += lazy[pos];
		maxVal[2*pos + 1] += lazy[pos];
		lazy[2*pos + 1] += lazy[pos];
		lazy[pos] = 0;
	}
	
	void rangeAdd(int a, int b, int l, int r, int pos, long long val){
		if(b < l || r < a)return;
		if(a <= l && r <= b){
			minVal[pos] += val; maxVal[pos] += val;
			lazy[pos] += val;
		}else{
			int m = (l + r) / 2;
			push(pos);
			rangeAdd(a, b, l, m, 2*pos, val);
			rangeAdd(a, b, m+1, r, 2*pos + 1, val);
			update(pos, false);
		}
	}
	
	public:
	Tree(int n){
		while(lrSize < n)lrSize *= 2;
		maxVal.resize(2*lrSize, 0);
		minVal.resize(2*lrSize, 0);
		lazy.resize(2*lrSize, 0);
	}
	
	void add(int a, long long val){
		rangeAdd(a, lrSize-1, 0, lrSize-1, 1, val);
	}
	
	long long getAns(long long c){
		long long maxV = -INF;
		long long minV = INF;
		int pos = 1;
		while(pos < lrSize){
			push(pos);
			if(max(maxVal[2*pos + 1], maxV) - min(minVal[2*pos + 1], minV) >= c){
				pos = 2*pos + 1;
			}else{
				maxV = max(maxV, maxVal[2*pos + 1]);
				minV = min(minV, minVal[2*pos + 1]);
				pos = 2 * pos;
			}
		}
		long long val1 = minVal[pos];
		pos = 1;
		while(pos < lrSize){
			push(pos);
			pos = 2*pos + 1;
		}
		long long val2 = minVal[pos];
		//cout<<"Debug info "<<val1<<" "<<val2<<"\n";
		if(val1 < minV){
			return c - (maxV - val2);
		}else{
			return (val2 - minV);
		}
	}
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<int> s(n);
    vector<vector<int>> add(n);
    vector<vector<int>> remove(n);
    for(int i = 0; i < q; i++){
		add[l[i]].push_back(i);
		remove[r[i]].push_back(i);
	}
	Tree tree(q + 2);
	tree.add(0, INF);
	tree.add(1, -INF);
	for(int i = 0; i < n; i++){
		for(auto x : add[i]){
			tree.add(x + 2, v[x]);
		}
		s[i] = tree.getAns(c[i]);
		for(auto x : remove[i]){
			tree.add(x+2, -v[x]);
		}
	}
	return s;
}

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