제출 #791272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791272		IvanJ	사탕 분배 (IOI21_candies)	C++17	100 / 100	1823 ms	42212 KiB

candies

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

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, inf = 1e9;
const ll INF = 1e18;

struct Data {
	ll lo, hi;
	int min_idx;
};

Data merge(Data A, Data B) {
	Data ret = {INF, -INF, -1};
	ret.lo = min(A.lo, B.lo);
	ret.hi = max(A.hi, B.hi);
	ret.min_idx = A.min_idx;
	if(ret.lo == B.lo)
		ret.min_idx = B.min_idx;
	return ret;
}

struct Seg {
	int pot = 1, n;
	vector<Data> T;
	vector<ll> L;
	void init(int _n) {
		n = _n;
		while(pot < n) pot <<= 1;
		for(int i = 0;i < (pot << 1);i++) T.pb({0, 0, -1}), L.pb(0);
		for(int i = 0;i < n;i++) T[i + pot].min_idx = i;
		for(int i = pot - 1;i > 0;i--) 
			T[i] = merge(T[i * 2], T[i * 2 + 1]);
	}
	
	void prop(int x) {
		if(L[x] == 0) return;
		T[x].lo += L[x];
		T[x].hi += L[x];
		if(x < pot) 
			L[x * 2] += L[x], L[x * 2 + 1] += L[x];
		L[x] = 0;
	}
	
	void add(int x, int lo, int hi, int a, int b, ll v) {
		prop(x);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			L[x] += v;
			prop(x);
			return;
		} 
		int mid = (lo + hi) / 2;
		add(x * 2, lo, mid, a, b, v);
		add(x * 2 + 1, mid + 1, hi, a, b, v);
		T[x] = merge(T[x * 2], T[x * 2 + 1]);
	}
	
	void update(int x, ll v) {add(1, 0, pot - 1, x, n - 1, v);}
	
	Data get_min(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return {INF, -INF, -1};
		if(a <= lo && hi <= b) return T[x];
		int mid = (lo + hi) / 2;
		Data l = get_min(x * 2, lo, mid, a, b);
		Data r = get_min(x * 2 + 1, mid + 1, hi, a, b);
		if(l.min_idx == -1) return r;
		if(r.min_idx == -1) return l;
		if(l.lo < r.lo) return l;
		return r;
	}
	
	int query(int lo, int hi) {return get_min(1, 0, pot - 1, lo, hi).min_idx;}
	
	Data get_range(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return {INF, -INF, -1};
		if(a <= lo && hi <= b) return T[x];
		int mid = (lo + hi) / 2;
		Data l = get_range(x * 2, lo, mid, a, b);
		Data r = get_range(x * 2 + 1, mid + 1, hi, a, b);
		return merge(l, r);
	}
	
	Data query2(int lo, int hi) {return get_range(1, 0, pot - 1, lo, hi);}
	
	int solve(ll c) {
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi) {
			int mid = (lo + hi) / 2;
			Data D = query2(mid, n - 1);
			//cout << mid << " -> " << D.lo << " " << D.hi << " mid\n";
			if(D.hi - D.lo < c) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		return ans;
	}
	
	ll get_val(int x, int lo, int hi, int X) {
		prop(x);
		if(lo == hi) return T[x].lo;
		int mid = (lo + hi) / 2;
		if(X <= mid) return get_val(x * 2, lo, mid, X);
		return get_val(x * 2 + 1, mid + 1, hi, X);
	}
	
	ll get(int x) {return get_val(1, 0, pot - 1, x);}
};

int n, q;
vector<ii> sweep[maxn];
Seg S;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = (int)c.size();
    q = (int)l.size();
    S.init(q + 2);
    vector<int> ans(n, 0);
    
    for(int i = 0;i < q;i++) 
		sweep[l[i]].pb({v[i], i + 2}), sweep[r[i] + 1].pb({-v[i], i + 2});
	
	S.update(0, inf);
	S.update(1, -inf);
	for(int i = 0;i < n;i++) {
		for(ii p : sweep[i]) 
			S.update(p.y, p.x);
		
		//for(int j = 0;j < q + 2;j++) 
		//	cout << S.get(j) << " ";
		//cout << "\n";
		
		int t_max = S.solve(c[i]);
		//cout << t_max << " tmax\n";
		ll h1 = S.get(t_max - 1), h2 = S.get(t_max);
		Data D = S.query2(t_max, q + 1);
		ll X = 0;
		X = c[i] - (D.hi - D.lo);
		if(h1 > h2) X = 0;
		int mini = S.query(t_max, q + 1);
		
		//cout << S.get(mini) << " " << S.get(q + 1) << " " << X << " X\n";
		ans[i] = S.get(q + 1) - S.get(mini) + X;
		//cout << "\n\n";
	}
    return ans;
}

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