oj.uz

Submission #1043684

# Submission time Handle Problem Language Result Execution time Memory
1043684 2024-08-04T13:48:56 Z 42kangaroo Distributing Candies (IOI21_candies) C++17
29 / 100
 295 ms 45984 KB 
#include "candies.h"
#include "bits/stdc++.h"

using namespace std;

struct Val {
	long long mi, miPo, ma, maPo;
};

Val operator+(const Val& l, const Val& r) {
	Val re{min(l.mi, r.mi), 0, max(l.ma, r.ma), 0};
	if (l.mi < r.mi) re.miPo = l.miPo;
	else re.miPo = r.miPo;
	if (l.ma >= r.ma) re.maPo = l.maPo;
	else re.maPo = r.maPo;
	return re;
}

struct SegTe {
	vector<long long> la;
	vector<Val> a;

	void push(int i) {
		if (la[i] != 0) {
			a[i].mi += la[i];
			a[i].ma += la[i];
			if (2*i + 2 < a.size()) {
				la[2*i + 1] += la[i];
				la[2*i + 2] += la[i];
			}
			la[i] = 0;
		}
	}

	Val build(int l, int r, int i, vector<long long>& in) {
		if (l + 1 == r) return a[i] = {in[l], l, in[l], l};
		int m = (l + r)/2;
		return a[i] = build(l, m, 2*i + 1, in) + build(m, r, 2*i + 2, in);
	}

	Val decr(int l, int r, int i, int lq, int rq, long long v) {
		push(i);
		if (rq <= l || r <= lq) return a[i];
		if (lq <= l && r <= rq) {
			la[i] += v;
			push(i);
			return a[i];
		}
		int m = (l + r)/2;
		return a[i] = decr(l, m, 2*i + 1, lq, rq,v) + decr(m, r, 2*i + 2, lq, rq, v);
	}

	Val get(int l, int r, int i, int k) {
		push(i);
		if (r <= k) return {(long long)1e18, -1, -1, -1};
		if (l >= k) return a[i];
		int m = (l + r)/2;
		return get(l, m, 2*i + 1, k) + get(m, r, 2*i + 2, k);
	}

	pair<int, long long> neHi(int l, int r, int i, int k, long long hi) {
		push(i);
		if (r <= k || a[i].ma <= hi) return {-1, -1};
		if (l + 1 == r) return {l, a[i].ma};
		int m = (l + r)/2;
		auto ri = neHi(l, m, 2*i + 1, k, hi);
		if (ri.first != -1) return ri;
		return neHi(m, r, 2*i + 2, k, hi);
	}
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
	int n = c.size(), m = v.size();
	std::vector<int> s(n, 0);
	vector<long long> ves(m + 1);
	int ind = 0;
	for (int i = 0; i < v.size(); ++i) {
		ves[i + 1] = ves[i] + v[i];
		if (ves[i + 1] <= 0)  {
			ind = i + 1;
			ves[i + 1] = 0;
		}
	}
	SegTe se{vector<long long>(4*m + 4, 0), vector<Val>(4*m + 4)};
	se.build(0, m + 1, 0, ves);
	vector<int> o(n);
	std::iota(o.begin(), o.end(),0);
	std::sort(o.begin(), o.end(), [&](int l, int r){return c[l] > c[r];});
	for (int i = 0; i < n; ++i) {
		int in = o[i];
		pair<int, long long> nex;
		while ((nex = se.neHi(0, m + 1, 0, ind, c[in])).first != -1) {
			Val neMis = se.get(0, m + 1, 0, nex.first);
			long long ch = min(nex.second - c[in], neMis.mi);
			se.decr(0, m + 1, 0, nex.first, m + 1, -ch);
			if (ch == neMis.mi) ind = neMis.miPo;
		}
		s[in] = se.get(0, m+ 1, 0, m).ma;
	}
	return s;
}

Compilation message

candies.cpp: In member function 'void SegTe::push(int)':
candies.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Val>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    if (2*i + 2 < a.size()) {
      |        ~~~~~~~~^~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 36 ms 37872 KB Output is correct
4 Correct 62 ms 3928 KB Output is correct
5 Correct 119 ms 41040 KB Output is correct
6 Correct 131 ms 41040 KB Output is correct
7 Correct 170 ms 40948 KB Output is correct
8 Correct 112 ms 44368 KB Output is correct
9 Correct 93 ms 45984 KB Output is correct

Subtask #5
0 / 33.0

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