제출 #1308601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308601		SmuggingSpun	사탕 분배 (IOI21_candies)	C++20	11 / 100	238 ms	37272 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 2e5 + 5;
int c[lim], l[lim], r[lim], v[lim];
vector<int>event[lim];
struct Data{
	ll s, mi, ma;
	Data(){
		s = mi = ma = 0;
	}
	Data(int x){
		mi = min(0LL, s = x);
		ma = max(0, x);
	}
	friend Data operator +(Data a, Data b){
		Data c;
		c.s = a.s + b.s;
		c.mi = min(a.mi, a.s + b.mi);
		c.ma = max(a.ma, a.s + b.ma);
		return c;
	}
};
Data st[lim << 2];
void update(int id, int l, int r, int p, int x){
	if(l == r){
		st[id] = Data(x);
		return;
	}
	int m = (l + r) >> 1;
	if(m < p){
		update(id << 1 | 1, m + 1, r, p, x);
	}
	else{
		update(id << 1, l, m, p, x);
	}
	st[id] = st[id << 1] + st[id << 1 | 1];
}
Data get(int id, int l, int r, int u, int v){
	if(l > v || r < u){
		return Data();
	}
	if(u <= l && v >= r){
		return st[id];
	}
	int m = (l + r) >> 1;
	return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
}
vector<int>distribute_candies(vector<int>__c, vector<int>__l, vector<int>__r, vector<int>__v){
	int n = __c.size(), q = __l.size();
	for(int i = 0; i < n; i++){
		c[i] = __c[i];
	}
	for(int i = 0; i < q; i++){
		l[i] = __l[i];
		r[i] = __r[i];
		v[i] = __v[i];
	}
	vector<int>ans(n, 0);
	if(max(n, q) <= 2000){
		for(int i = 0; i < q; i++){
			for(int j = l[i]; j <= r[i]; j++){
				if(v[i] > 0){
					ans[j] = min(c[j], ans[j] + v[i]);
				}
				else{
					ans[j] = max(0, ans[j] + v[i]);
				}
			}
		}
		return ans;
	}
	if(*min_element(__v.begin(), __v.end()) > 0){
		vector<ll>f(n + 1, 0);
		for(int i = 0; i < q; i++){
			f[l[i]] += v[i];
			f[r[i] + 1] -= v[i];
		}
		ans[0] = min(ll(c[0]), f[0]);
		for(int i = 1; i < n; i++){
			ans[i] = min(ll(c[i]), f[i] += f[i - 1]);
		}
		return ans;
	}
	for(int i = 0; i < q; i++){
		event[l[i]].push_back(i);
		event[r[i] + 1].push_back(-i - 1);
	}
	set<int>sq;
	for(int i = 0; i < n; i++){
		for(int& j : event[i]){
			if(j < 0){
				int x = -j - 1;
				sq.erase(x);
				update(1, 0, q - 1, x, 0);
			}
			else{
				sq.insert(j);
				update(1, 0, q - 1, j, v[j]);
			}
		}
		if(!sq.empty()){
			int low = 0, high = q - 1;
			while(low <= high){
				int mid = (low + high) >> 1;
				Data vl = get(1, 0, q - 1, mid, q - 1);
				set<int>::iterator sq_it = sq.lower_bound(mid);
				bool at0 = (sq_it == sq.begin() || v[*prev(sq_it)] < 0);
				if(at0){
					if(vl.mi < 0 || vl.ma > c[i]){
						low = mid + 1;
					}
					else{
						ans[i] = vl.ma;
						high = mid - 1;
					}
				}
				else if(vl.ma > 0 || vl.mi < -c[i]){
					low = mid + 1;
				}
				else{
					ans[i] = c[i] + vl.mi;
					high = mid - 1;
				}
			}
		}
	}
	return ans;
}

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