Submission #896745

#	Time	Username	Problem	Language	Result	Execution time	Memory
896745		Jawad_Akbar_JJ	사탕 분배 (IOI21_candies)	C++17	0 / 100	681 ms	51508 KiB

candies

#include <iostream>
#include <vector>
#include "candies.h"

using namespace std;

const int N = (1<<18) + 1;

vector<pair<int,int>> L[N];
vector<pair<int,int>> R[N];








// ######################################### starts prefix-seg ######################
long long Mn = 0,Mx = 0;

struct node{
	long long mn = 0;
	long long mx = 0;
	long long lazy = 0;
} seg[N<<2];

void push(int cur,int lc,int rc,int mid,int st){
	seg[lc].mn += seg[cur].lazy;
	seg[rc].mn += seg[cur].lazy;
	seg[lc].mx += seg[cur].lazy;
	seg[rc].mx += seg[cur].lazy;
	seg[lc].lazy += seg[cur].lazy;
	seg[rc].lazy += seg[cur].lazy;
	seg[cur].lazy = 0;
}

node merge(node a,node b){
	node res;
	res.mx = max(a.mx,b.mx);
	res.mn = min(a.mn,b.mn);
	return res;
}

void insert(int l,int r,int v,int cur = 1,int st = 1,int en = N){
	if (l<=st and r>=en){
		seg[cur].mx += v;
		seg[cur].mn += v;
		seg[cur].lazy += v;
		return;
	}
	
	if (en<=l or st>=r)
		return;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;

	push(cur,lc,rc,mid,st);

	insert(l,r,v,lc,st,mid);
	insert(l,r,v,rc,mid,en);

	seg[cur] = merge(seg[lc],seg[rc]);
}

void get(int l,int r,int cur = 1,int st = 1,int en = N){
	if (st==1 and en == N){
		Mn = 1e9;
		Mx = -1e9;
	}
	if (l<=st and r>=en){
		Mn = min(Mn,seg[cur].mn);
		Mx = max(Mx,seg[cur].mx);
		return;
	}
	if (en<=l or st>=r)
		return;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;
	push(cur,lc,rc,mid,st);
	get(l,r,lc,st,mid);
	get(l,r,rc,mid,en);
}

// ######################################### ends prefix-seg ######################







// ##################  starts sum  #######################

struct nodes{
	long long sum = 0;
} seg2[N<<2];


void insert2(int i,int v,int cur = 1,int st = 1,int en = N){
	if (en<=i or st>i)
		return;
	if (en - st == 1){
		seg2[cur].sum += v;
		return;
	}

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;

	insert2(i,v,lc,st,mid);
	insert2(i,v,rc,mid,en);

	seg2[cur].sum = seg2[lc].sum + seg2[rc].sum;
}

long long get2(int l,int r,int cur = 1,int st = 1,int en = N){

	if (l<=st and r>=en)
		return seg2[cur].sum;
	
	if (en<=l or st>=r)
		return 0;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;
	return get2(l,r,lc,st,mid) + get2(l,r,rc,mid,en);
}

// ######################### ends sum ###########


bool valid(int i,int d){
	get(i,N);
	return (Mx - Mn >= d);
}

vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){
	int n = c.size();
	int m = l.size();

	for (int i=0;i<m;i++){
		L[l[i]+1].push_back({v[i],i+2});
		R[r[i]+1].push_back({-v[i],i+2});
	}
	vector<int> ans;
	for (int i=1;i<=n;i++){
		for (auto [val,t] : R[i-1]){
			insert(t,N,val);
			insert2(t,val);
		}
		for (auto [val,t] : L[i]){
			insert(t,N,val);
			insert2(t,val);
		}

		int l = 1,r = N;
		get(1,N);
		if (Mx - Mn < c[i-1]){
			ans.push_back(get2(1,N) - Mn);//////////////////////////// wrong alert
			continue;
		}

		while (l + 1 < r){
			int md = (l + r)/2;
			if (valid(md,c[i-1]))
				l = md;
			else
				r = md;
		}
		if (valid(r,c[i-1]))
			l = r;

		get(l,N);

		// cout<<i<<" "<<l<<" "<<Mn<<" "<<Mx<<endl;

		// get(1,N);
		// cout<<Mn<<" "<<Mx<<endl;

		long long mx = Mx;

		long long base = Mx - c[i-1];

		get(l+1,N);
		// cout<<"Mx Mn "<<Mx<<" "<<Mn<<endl;
		long long Sum = get2(1,N);
		if (Mx != mx)
			base = Mn;

		// cout<<"sum l+1 N"<<Sum<<endl;
		// cout<<"base "<<base<<endl;
		ans.push_back(Sum - base);
		// break;
	}
	return ans;

}

// int main(){
// 	int n,m;
// 	cin>>n;

// 	vector<int> c(n);

// 	for (int i=0;i<n;i++)
// 		cin>>c[i];

// 	cin>>m;

// 	vector<int> l(m),r(m),v(m);

// 	for (int i=0;i<m;i++)
// 		cin>>l[i]>>r[i]>>v[i];

// 	vector<int> ans = distribute_candies(c,l,r,v);
// 	for (int i : ans)
// 		cout<<i<<" ";
// 	cout<<endl;
// 	return 0;
// }

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