oj.uz

Submission #435591

# Submission time Handle Problem Language Result Execution time Memory
435591 2021-06-23T12:56:35 Z Noam527 Distributing Candies (IOI21_candies) C++17
100 / 100
 1016 ms 35596 KB 
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 3e18;
const int OO = 1;
using namespace std;

#include "candies.h"

struct info {
	ll mn, mx;
	int imn, imx;
	info() {
		mn = inf;
		mx = -inf;
		imn = imx = -1;
	}
	info(int index) {
		mn = mx = 0;
		imn = imx = index;
	}
	void use(const info &a) {
		if (mn > a.mn) {
			mn = a.mn;
			imn = a.imn;
		}
		if (mx < a.mx) {
			mx = a.mx;
			imx = a.imx;
		}
	}
};
void comb(info &a, const info b, const info &c) {
	a = b;
	a.use(c);
}
void pr(const info &a) {
	printf("(%lld, %d), (%lld, %d)\n", a.mn, a.imn, a.mx, a.imx);
}

// index 0 is saved! ye.
struct segtree {
	int n;
	vector<ll> tag;
	vector<info> t;
	segtree() {}
	segtree(int sz) {
		n = max(2, sz + 1);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
		tag.resize(2 * n, 0);
		for (int i = 0; i < n; i++) {
			t[i + n - 1] = info(i);
		}
		for (int i = n - 2; i >= 0; i--) {
			comb(t[i], t[2 * i + 1], t[2 * i + 2]);
		}
	}
	void push(int x) {
		t[x].mn += tag[x], t[x].mx += tag[x];
		if (x < n - 1) {
			tag[2 * x + 1] += tag[x];
			tag[2 * x + 2] += tag[x];
		}
		tag[x] = 0;
	}
	void fix(int x) {
		push(2 * x + 1), push(2 * x + 2);
		comb(t[x], t[2 * x + 1], t[2 * x + 2]);
	}
	void add(int l, int v) {
		add(l, n - 1, v, 0, 0, n - 1);
	}
	void add(int l, int r, int v) {
		add(l, r, v, 0, 0, n - 1);
	}
	void add(int l, int r, int v, int node, int nl, int nr) {
		if (nr < l || r < nl) return;
		if (l <= nl && nr <= r) {
			tag[node] += v;
			return;
		}
		push(node);
		int mid = (nl + nr) / 2;
		add(l, r, v, 2 * node + 1, nl, mid);
		add(l, r, v, 2 * node + 2, mid + 1, nr);
		fix(node);
	}
	info minimix(int l, int r) {
		if (l > r) return info();
		return minimix(l, r, 0, 0, n - 1);
	}
	info minimix(int l, int r, int node, int nl, int nr) {
		if (nr < l || r < nl) return info();
		push(node);
		if (l <= nl && nr <= r) {
			return t[node];
		}
		info res = info();
		int mid = (nl + nr) / 2;
		res.use(minimix(l, r, 2 * node + 1, nl, mid));
		res.use(minimix(l, r, 2 * node + 2, mid + 1, nr));
		return res;
	}
	info suffix(ll c) {
		push(0);
		if (t[0].mx - t[0].mn < c) return info();
		info cur = info(), tmp;
		int node = 0, nl = 0, nr = n - 1;
		while (node < n - 1) {
			int mid = (nl + nr) / 2;
			int left = 2 * node + 1, right = 2 * node + 2;
			push(left), push(right);
			comb(tmp, cur, t[right]);
			if (tmp.mx - tmp.mn < c) {
				cur = tmp;
				node = left;
				nr = mid;
			}
			else {
				node = right;
				nl = mid + 1;
			}
		}
		cur.use(t[node]);
		return cur;
	}
	ll get(int x) {
		int node = 0, nl = 0, nr = n - 1;
		while (node < n - 1) {
			push(node);
			int mid = (nl + nr) / 2;
			if (x <= mid) {
				nr = mid;
				node = 2 * node + 1;
			}
			else {
				nl = mid + 1;
				node = 2 * node + 2;
			}
		}
		push(node);
		return t[node].mn;
	}
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size();
	int q = l.size();
	segtree T(q);
	vector<int> result(n);
	vector<vector<pair<int, int>>> upd(n);
	for (int i = 0; i < l.size(); i++) {
		int tim = i + 1;
		int val = v[i];
		upd[l[i]].emplace_back(tim, val);
		if (r[i] + 1 < n)
			upd[r[i] + 1].emplace_back(tim, -val);
	}
	for (int i = 0; i < n; i++) {
		for (const auto &p : upd[i]) {
			T.add(p.first, p.second);
		}
		info cur = T.suffix(c[i]);
		if (cur.imn == -1) {
			cur = T.minimix(0, q);
			if (cur.mn < 0)
				result[i] = T.get(q) - cur.mn;
			else
				result[i] = T.get(q);
		}
		else if (cur.imn < cur.imx) {
			result[i] = c[i] - (cur.mx - T.get(q));
		}
		else {
			result[i] = T.get(q) - cur.mn;
		}
	}
	return result;
}

void solve() {

	int n, q;
	cin >> n >> q;
	vector<int> c(n), l(q), r(q), v(q);
	for (auto &i : c) cin >> i;
	for (auto &i : l) cin >> i;
	for (auto &i : r) cin >> i;
	for (auto &i : v) cin >> i;
	vector<int> result = distribute_candies(c, l, r, v);
	for (const auto &i : result) cout << i << " "; cout << '\n';

	/*
	int n;
	cin >> n;
	segtree T(n);
	while (1) {
		string op;
		int l, r, v;
		cin >> op;
		if (op == "add") {
			cin >> l >> v;
			T.add(l, v);
		}
		else if (op == "minimix") {
			cin >> l >> r;
			info res = T.minimix(l, r);
			printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
		}
		else if (op == "suffix") {
			cin >> v;
			info res = T.suffix(v);
			printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
		}
	}
	*/
}
/*
int main() {
	//ios::sync_with_stdio(0), cin.tie(0);
	int tst = 1;
	//cin >> tst;
	while (tst--) solve();
}
*/

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < l.size(); i++) {
      |                  ~~^~~~~~~~~~
candies.cpp: In function 'void solve()':
candies.cpp:193:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  193 |  for (const auto &i : result) cout << i << " "; cout << '\n';
      |  ^~~
candies.cpp:193:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  193 |  for (const auto &i : result) cout << i << " "; cout << '\n';
      |                                                 ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 35492 KB Output is correct
2 Correct 906 ms 35448 KB Output is correct
3 Correct 1016 ms 35480 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 598 ms 25952 KB Output is correct
3 Correct 133 ms 7620 KB Output is correct
4 Correct 861 ms 35496 KB Output is correct
5 Correct 906 ms 35496 KB Output is correct
6 Correct 869 ms 35596 KB Output is correct
7 Correct 829 ms 35512 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 211 ms 23632 KB Output is correct
4 Correct 109 ms 7476 KB Output is correct
5 Correct 347 ms 30548 KB Output is correct
6 Correct 329 ms 30548 KB Output is correct
7 Correct 351 ms 30580 KB Output is correct
8 Correct 360 ms 30648 KB Output is correct
9 Correct 386 ms 30648 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 924 ms 35492 KB Output is correct
7 Correct 906 ms 35448 KB Output is correct
8 Correct 1016 ms 35480 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 598 ms 25952 KB Output is correct
11 Correct 133 ms 7620 KB Output is correct
12 Correct 861 ms 35496 KB Output is correct
13 Correct 906 ms 35496 KB Output is correct
14 Correct 869 ms 35596 KB Output is correct
15 Correct 829 ms 35512 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 211 ms 23632 KB Output is correct
19 Correct 109 ms 7476 KB Output is correct
20 Correct 347 ms 30548 KB Output is correct
21 Correct 329 ms 30548 KB Output is correct
22 Correct 351 ms 30580 KB Output is correct
23 Correct 360 ms 30648 KB Output is correct
24 Correct 386 ms 30648 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 124 ms 7600 KB Output is correct
27 Correct 599 ms 25960 KB Output is correct
28 Correct 923 ms 35528 KB Output is correct
29 Correct 850 ms 35504 KB Output is correct
30 Correct 919 ms 35492 KB Output is correct
31 Correct 911 ms 35500 KB Output is correct
32 Correct 867 ms 35548 KB Output is correct