제출 #601348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601348		1ne	Distributing Candies (IOI21_candies)	C++17	0 / 100	110 ms	12024 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
struct dataa{
	long long prefsum = 0,prefmax = 0,prefmin = 0,lazy =0,lazymin = 0,lazymax = 0,ans = 0;
	bool prefindex = 0,lazyindex = 0;
	void add(long long left,long long right,long long val){
		prefsum += val * (right - left + 1);
		lazy += val * (right - left + 1);
		if (prefsum > prefmax){
			prefmax = prefsum;
			prefindex = 1;
		}
		else if (prefsum < prefmin){
			prefmin = prefsum;
			prefindex = 0;
		}
	}
};
struct Segment_Tree{
	vector<dataa>tree;
	void init(long long n){
		tree.resize(2*n - 1);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		res.prefsum = left.prefsum + right.prefsum;
		res.prefmax = max({res.prefsum,left.prefsum + right.prefmax,left.prefmax,right.prefmax});
		res.prefmin = min(res.prefsum,left.prefsum);
		return res;
	}
	void push(long long node,long long left,long long right){
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (tree[node].lazy!=0){
			tree[node + 1].add(left,mid,tree[node].lazy);
			tree[z].add(mid + 1,right,tree[node].lazy);
			tree[node].lazy = 0;
		}
	}
	dataa query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return {0,0,0,0,0};
		if (qleft<=left && qright>=right){
			return tree[node];
		}
		push(node,left,right);
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			tree[node].add(left,right,v);
			return;
		}
		push(node,left,right);
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,v);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,v);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = (int)c.size();
    vector<int>ans(n);
    int m = (int)l.size();
    vector<long long>pref(m + 1);
    pref[0] = 0;
    for (int i = 0;i<m;++i){
		pref[i + 1] = pref[i] + v[i];
	 }
	 vector<long long>suff_max(m + 1),suff_min(m + 1); 
	 suff_max[m] = pref[m];
	 suff_min[m] = pref[m];
	 for (int i = m - 1;i >=0;--i){
		suff_max[i] = max(suff_max[i + 1],pref[i]);
		suff_min[i] = min(suff_min[i + 1],pref[i]);
	 }
	 for (int i = 0;i<n;++i){
		int left = 0,right = m;	
		int p = -1;
		while(left<=right){
			int mid = (left + right)>>1;
			if (suff_max[mid] - suff_min[mid] >= c[i]){
				left = mid + 1;
				p = mid;
			}
			else right = mid - 1;
		}
		if (p == -1){
			ans[i] = pref[m];
		}
		else if (suff_max[p] == pref[p]){
			ans[i] = max(0LL,pref[m] - suff_max[p] + c[i]);
		}
		else{
			ans[i] = max(0LL,pref[m] - suff_min[p]);
		}
	 }
	 return ans;
}

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