Submission #923405

#	Time	Username	Problem	Language	Result	Execution time	Memory
923405		Edwin0319	사탕 분배 (IOI21_candies)	C++17	100 / 100	290 ms	36628 KiB

candies

#include "candies.h"
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

typedef struct {
	int l;
	int r;
	ll sum;
	ll min_sum;
	ll max_sum;
} Node;

typedef struct {
	int id;
	int pos;
	int val;
} Query;

Node tree[800007];
Query query[400007];

bool operator <(const Query a, const Query b){
	return a.pos < b.pos;
}

void build(int x, int l, int r){
	tree[x].l = l;
	tree[x].r = r;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
}

inline void update(int x){
	int ls = x * 2, rs = x * 2 + 1;
	tree[x].sum = tree[ls].sum + tree[rs].sum;
	tree[x].min_sum = min(tree[ls].min_sum, tree[rs].min_sum + tree[ls].sum);
	tree[x].max_sum = max(tree[ls].max_sum, tree[rs].max_sum + tree[ls].sum);
}

void add(int x, int pos, int val){
	if (tree[x].l == tree[x].r){
		tree[x].sum += val;
		tree[x].min_sum = min(tree[x].sum, 0ll);
		tree[x].max_sum = max(tree[x].sum, 0ll);
		return;
	}
	if (pos <= ((tree[x].l + tree[x].r) >> 1)){
		add(x * 2, pos, val);
	} else {
		add(x * 2 + 1, pos, val);
	}
	update(x);
}

ll do_query(int x, int k, ll cur_sum, ll cur_min_sum, ll cur_max_sum){
	if (tree[x].l == tree[x].r) return (tree[x].sum <= 0 && cur_max_sum > k) || (tree[x].sum > 0 && cur_min_sum >= -k) ? k + cur_sum - cur_max_sum : cur_sum - cur_min_sum;
	int rs = x * 2 + 1;
	ll y = min(tree[rs].min_sum, cur_min_sum + tree[rs].sum), z = max(tree[rs].max_sum, cur_max_sum + tree[rs].sum);
	if (z - y > k) return do_query(rs, k, cur_sum, cur_min_sum, cur_max_sum);
	return do_query(x * 2, k, cur_sum + tree[rs].sum, y, z);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
	int n = c.size(), q = l.size(), m = 0;
	vector<int> ans;
	c.insert(c.begin(), 0);
	l.insert(l.begin(), 0);
	r.insert(r.begin(), 0);
	v.insert(v.begin(), 0);
	build(1, 0, q);
	for (register int i = 1; i <= q; i++){
		m++;
		query[m].id = i;
		query[m].pos = ++l[i];
		query[m].val = v[i];
		if (++r[i] < n){
			m++;
			query[m].id = i;
			query[m].pos = r[i] + 1;
			query[m].val = -v[i];
		}
	}
	sort(query + 1, query + m + 1);
	for (register int i = 1, j = 1; i <= n; i++){
		while (j <= m && query[j].pos == i){
			add(1, query[j].id, query[j].val);
			j++;
		}
		ans.push_back(do_query(1, c[i], 0, 0, 0));
	}
	return ans;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:77:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   77 |  for (register int i = 1; i <= q; i++){
      |                    ^
candies.cpp:90:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   90 |  for (register int i = 1, j = 1; i <= n; i++){
      |                    ^
candies.cpp:90:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   90 |  for (register int i = 1, j = 1; i <= n; i++){
      |                           ^

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