제출 #1243521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243521		ansori	사탕 분배 (IOI21_candies)	C++20	100 / 100	314 ms	34408 KiB

candies

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MN = 2e5 + 5;
const ll inf = 1e16;
struct def{
	ll mx , mn;
};
int n , q;
ll lz[MN * 4];
vector<def> t(MN * 4);
def kur;
def mrg(def a , def b){
	return {max(a.mx , b.mx) , min(a.mn , b.mn)};
}
void push(int v){
	if(! lz[v])	return ;
	lz[v * 2] += lz[v];
	t[v * 2] = {t[v * 2].mx + lz[v] , t[v * 2].mn + lz[v]};
	lz[v * 2 + 1] += lz[v];
	t[v * 2 + 1] = {t[v * 2 + 1].mx + lz[v] , t[v * 2 + 1].mn + lz[v]};
	lz[v] = 0;
}
void upd(int v , int l , int r , int l1 , int r1 , int val){
	if(l <= l1 and r1 <= r){
		lz[v] += val;
		t[v] = {t[v].mx + val , t[v].mn + val};
		return ;
	}	
	if(r1 - l1 > 1) push(v);
	int m = (l1 + r1) / 2;
	if(l1 < r and l < m) upd(v * 2 , l , r , l1 , m , val);
	if(m < r and l < r1) upd(v * 2 + 1 , l , r , m , r1 , val);
	t[v] = mrg(t[v * 2] , t[v * 2 + 1]);
}
int get(int v , int l , int r , ll dif){
	if(r - l == 1) return l;
	push(v);
	def nk = mrg(t[v * 2 + 1] , kur);
	int m = (l + r) / 2;
	if(nk.mx - nk.mn <= dif){
		kur = nk;
		return get(v * 2 , l , m , dif);
	} 
	else return get(v * 2 + 1 , m , r , dif);
}
int gett(int dif){
	kur = {-inf , inf};
	return get(1 , 0 , q + 1 , dif);	
} 
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v){
	n = c.size() , q = l.size();
	vector<int> ans(n , 0);
	vector<int> iv[n + 1];
	for(int i = 0;i < q; ++ i){
		iv[l[i]].push_back(i);
		iv[r[i] + 1].push_back(i);
	}
	ll height = 0;
	for(int i = 0;i < n; ++ i){
		for(auto to : iv[i]){
			if(l[to] == i){
				upd(1 , to + 1 , q + 1 , 0 , q + 1 , v[to]);
				height += v[to];	
			}
			else{
				upd(1 , to + 1 , q + 1 , 0 , q + 1 , -v[to]);
				height -= v[to];	
			}
		}
		if(t[1].mx - t[1].mn <= c[i]) ans[i] = (height - t[1].mn);
		else{
			int ps = gett(c[i]);
			//cout << ps << ' ' << i << '\n';
			if(v[ps] > 0){
				ans[i] = height - (kur.mx - c[i]);
			}
			else{
				ans[i] = height - kur.mn;
			}
		}
	}
	return ans;
}

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