oj.uz

Submission #587145

# Submission time Handle Problem Language Result Execution time Memory
587145 2022-07-01T11:39:58 Z AkramElOmrani Distributing Candies (IOI21_candies) C++17
8 / 100
 106 ms 12884 KB 
#include "candies.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;

void apply(int& v, int a, int mx) {
	ll res = v; res += a;
	res = max(res, 0LL);
	res = min(res, (ll)mx);
	v = res;
}

vector<ll> tree, lazy;

void process(int node, int l, int r, vector<int>& c) {
	if(lazy[node] != 0) {
		if(l != r) 
			for(int x : {node * 2, node * 2 + 1})
				lazy[x] += lazy[node];
	}
	lazy[node] = 0;
}

void upd(int node, int l, int r,
		int low, int high, int v, vector<int>& c) {
	process(node, l, r, c);
	if(low <= l && r <= high) {
		lazy[node] += v;
		process(node, l, r, c);
		return;
	}
	int mid = (l + r) / 2;
	upd(node * 2, l, mid, low, high, v, c);
	upd(node * 2 + 1, mid + 1, r, low, high, v, c);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];	
}

vector<int> ans;

void reverse_build(int node, int l, int r) {
	if(l == r) {
		ans[l] = tree[node];
		return;
	}
	int mid = (l + r) / 2;
	reverse_build(node * 2, l, mid);
	reverse_build(node * 2 + 1, mid + 1, r);
}

vector<int> distribute_candies(vector<int> c,
		vector<int> l,
		vector<int> r,
		vector<int> v) {

	int n = c.size();
	int q = l.size();

	vector<ll> ans(n + 1);

	for(int i = 0; i < q; ++i) {
		ans[l[i]] += v[i];
		ans[r[i] + 1] -= v[i];
	}
	for(int i = 1; i <= n; ++i) {
		ans[i] += ans[i - 1];
	}
	vector<int> s(n);
	for(int i = 0; i < n; ++i) {
		s[i] = min((ll)c[i], max((ll)s[i], ans[i]));
	}

	return s;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 9832 KB Output is correct
2 Correct 98 ms 12884 KB Output is correct
3 Correct 88 ms 12760 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -