제출 #827167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827167		NothingXD	사탕 분배 (IOI21_candies)	C++17	0 / 100	352 ms	43724 KiB

candies

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int lg = 20;

int n, q, a[maxn], c[maxn], f[maxn];
pll seg[maxn << 2];
pll lazy[maxn << 2];

void add(int idx, int x){
	for (; idx <= q; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

int find(int x){
	int res = 0;
	for (int i = lg-1; ~i; i--){
		int idx = (res + (1 << i));
		if (idx <= q && f[idx] < x){
			x -= f[idx];
			res = idx;
		}
	}
	return res+1;
}

pll operator +(pll a, pll b){
	return MP(min(a.F, b.F), max(a.S, b.S));
}

void shift(int v, int l, int r);

void add(int v, int l, int r, int ql, int qr, ll val){
//	if (v == 1) debug(ql, qr, val);
//	debug(v, l, r, ql, qr, val);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v].F += val;
		seg[v].S += val;
		lazy[v].F += val;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void reverse(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		swap(seg[v].F, seg[v].S);
		seg[v].F = -seg[v].F;
		seg[v].S = -seg[v].S;
		lazy[v].F = -lazy[v].F;
		lazy[v].S *= -1;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	reverse(v << 1, l, mid, ql, qr);
	reverse(v << 1 | 1, mid, r, ql, qr);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

ll get(int v, int l, int r, int idx){
	if (l + 1 == r) return seg[v].F;
	shift(v, l, r);
	int mid = (l + r) >> 1;
	if (idx < mid) return get(v << 1, l, mid, idx);
	return get(v << 1 | 1, mid, r, idx);
}

int find(int v, int l, int r, int ql, int qr, ll val){
//	debug(v, l, r, seg[v].F, seg[v].S, val);
	if (qr <= l || r <= ql) return -1;
	if (ql <= l && r <= qr && seg[v].F >= 0 && seg[v].S <= val) return -1;
	if (l + 1 == r) return l;
	shift(v, l, r);
	int mid = (l + r) >> 1;
	int res = find(v << 1, l, mid, ql, qr, val);
	if (res == -1) res = find(v << 1 | 1, mid, r, ql, qr, val);
	return res;
}

void shift(int v, int l, int r){
	if (lazy[v].F == 0 && lazy[v].S == 1) return;
	int mid = (l + r) >> 1;
	if (lazy[v].S != 1){
		reverse(v << 1, l, mid, l, mid);
		reverse(v << 1 | 1, mid, r, mid, r);
	}
	if (lazy[v].F != 0){
		add(v << 1, l, mid, l, mid, lazy[v].F);
		add(v << 1 | 1, mid, r, mid, r, lazy[v].F);
	}
	lazy[v] = {0, 1};
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
	n = C.size();
	q = L.size();
	vector<pii> num;
	for (int i = 0; i < 4*maxn; i++) lazy[i] = {0, 1};
	for (int i = 0; i < n; i++){
		c[i] = C[i];
		num.push_back({c[i], i});
	}
	set<pii> st;
	for (int i = 0; i < q; i++){
		add(1, 0, q, i, q, V[i]);
	}
	st.insert({0, q-1});
	sort(all(num), greater<pii>());
	for (auto [x, y]: num){
	//	debug(x, y);
		int tmp;
		while((tmp = find(1, 0, q, 0, q, x)) != -1){
	//		debug(tmp);
			int val = get(1, 0, q, tmp);
	//		debug(val);
			auto it = st.upper_bound({tmp, 0});
			it--;
			int L = (*it).F;
			int R = (*it).S;
			st.erase(it);
			if (L != tmp) st.insert({L, tmp-1});
			st.insert({tmp, R});
			add(1, 0, q, tmp, R+1, -val);
			if (val > x){
				reverse(1, 0, q, tmp, R+1);
				int idk = get(tmp+1);
				int idk2 = find(idk+1);
				if (idk2 != q+1) add(idk2, -1);
				add(tmp+1, 1);
			}
		}
		int res = get(1, 0, q, q-1);
		a[y] = ((get(q) & 1)? x-res:res);
	}
	vector<int> ans;
	for (int i = 0; i < n; i++){
		ans.push_back(a[i]);
	}
	return ans;
}

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