oj.uz

Submission #574399

# Submission time Handle Problem Language Result Execution time Memory
574399 2022-06-08T13:15:28 Z wjajjsasqq Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 12364 KB 
#include "candies.h"
#include <algorithm>
#include <cstdio>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

const int INF = 1070000000;

const int N = 200008;
int n, a[N], c[N], C, res[N];
long long inc[N];

std::vector<int> distribute_candies(std::vector<int> c_, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
	n = (int)c_.size();
	std::vector<int> ans(n);
	for (int i = 0; i < n; ++i) c[i] = c_[i];
	if (n <= 2000 && l.size() <= 2000) {
		for (int i = 0; i < (int)l.size(); ++i) {
			int ll = l[i], rr = r[i] + 1, d = v[i];
			for (int j = ll; j < rr; ++j) a[j] += d;
			if (d > 0) {
				for (int j = ll; j < rr; ++j) a[j] = a[j] < c[j] ? a[j] : c[j];
			} else {
				for (int j = ll; j < rr; ++j) a[j] = a[j] < 0 ? 0 : a[j];
			}
		}
		for (int i = 0; i < n; ++i) ans[i] = a[i];
	} else {
		bool pos = 1;
		for (int i = 0; i < (int)v.size(); ++i) if (v[i] < 0) pos = 0;
		if (pos) {
			for (int i = 0; i < (int)l.size(); ++i) {
				inc[l[i]] += v[i];
				inc[r[i] + 1] -= v[i];
			}
			for (int i = 0; i < n; ++i) {
				if (i) inc[i] += inc[i - 1];
				ans[i] = std::min((long long)c[i], inc[i]);
			}
		} else {
			C = c_[0];
			for (int i = 0; i < (int)l.size(); ++i) {
				int ll = l[i], rr = r[i] + 1, d = v[i];
				//for (int j = ll; j < rr; ++j) res[j] += d;
				if (d < 0) {
					for (int j = ll; j < rr; ++j) res[j] = res[j] + d < 0 ? 0 : res[j] + d;
				}
				else {
					for (int j = ll; j < rr; ++j) res[j] = res[j] + d < c[j] ? res[j] + d : c[j];
				}
			}
			for (int j = 0; j < n; ++j) ans[j] = res[j];
		}
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9660 KB Output is correct
2 Correct 93 ms 9696 KB Output is correct
3 Correct 101 ms 9696 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 78 ms 4972 KB Output is correct
3 Correct 72 ms 5408 KB Output is correct
4 Correct 2924 ms 8928 KB Output is correct
5 Correct 2730 ms 9008 KB Output is correct
6 Correct 2826 ms 8924 KB Output is correct
7 Correct 2865 ms 8928 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 110 ms 5060 KB Output is correct
4 Correct 124 ms 5564 KB Output is correct
5 Execution timed out 5085 ms 12364 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 95 ms 9660 KB Output is correct
7 Correct 93 ms 9696 KB Output is correct
8 Correct 101 ms 9696 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 78 ms 4972 KB Output is correct
11 Correct 72 ms 5408 KB Output is correct
12 Correct 2924 ms 8928 KB Output is correct
13 Correct 2730 ms 9008 KB Output is correct
14 Correct 2826 ms 8924 KB Output is correct
15 Correct 2865 ms 8928 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 110 ms 5060 KB Output is correct
19 Correct 124 ms 5564 KB Output is correct
20 Execution timed out 5085 ms 12364 KB Time limit exceeded
21 Halted 0 ms 0 KB -