제출 #1245074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245074		nicolo_010	사탕 분배 (IOI21_candies)	C++20	0 / 100	5090 ms	10564 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
template <typename T>
using ve = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i=k;i<n;i++)

ve<int> a;

struct SegTree {
	ve<int> lazy;
	SegTree (int n) {
		lazy.assign(4*n, 0);
	}

	void prop(int p, int l, int r) {
		if (l == r) {
			a[l] += lazy[p];
		}
		else {
			lazy[2*p] += lazy[p];
			lazy[2*p+1] += lazy[p];
		}
		lazy[p] = 0;
	}

	void query(int p, int l, int r, int i, int j, int k) {
		if (l > j || r < i) return;
		if (lazy[p]) prop(p, l, r);
		if (i <= l && r <= j) {
			lazy[p] += k;
		}
		else {
			query(2*p, l, (l+r)/2, i, j, k);
			query(2*p+1, (l+r)/2+1, r, i, j, k);
		}
	}

	void point(int p, int l, int r, int i) {
		if (lazy[p]) prop(p, l, r);
		if (l == r) return;
		else {
			point(2*p, l, (l+r)/2, i);
			point(2*p+1, (l+r)/2+1, r, i);
		}
	}
};

ve<int> distribute_candies(ve<int> c, ve<int> l, ve<int> r, ve<int> v) {
	int n = c.size();
	int q = l.size();
	a.assign(n, 0);
	SegTree st(n);
	rep(i, 0, q) {
		st.query(1, 0, n-1, l[i], r[i], v[i]);
	}
	rep(i, 0, n) {
		st.point(1, 0, n-1, i);
	}
	rep(i, 0, n) a[i] = min(a[i], c[i]);
	return a;
}

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