oj.uz

Submission #518743

# Submission time Handle Problem Language Result Execution time Memory
518743 2022-01-24T14:19:17 Z Asymmetry Distributing Candies (IOI21_candies) C++17
0 / 100
 367 ms 36164 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

struct node {
	long long mn, mx, ps;
};

int n, q, com, p;
long long mn, mx, all;
vector<node> st;

void ins(int x, int l, int r, int ll, int rr, int w) {
	if (l > rr || ll > r) {
		return;
	}
	if (ll <= l && r <= rr) {
		st[x].mx += w;
		st[x].mn += w;
		st[x].ps += w;
		return;
	}
	int ls = x << 1;
	ins(ls, l, (l + r) / 2, ll, rr, w);
	ins(ls ^ 1, (l + r) / 2 + 1, r, ll, rr, w);
	st[x].mx = max(st[ls].mx, st[ls ^ 1].mx) + st[x].ps;
	st[x].mn = min(st[ls].mn, st[ls ^ 1].mn) + st[x].ps;
}

void suf(int x, int w, long long add) {
	if (x >= com) {
		mn = min(mn, st[x].mn + add);
		mx = max(mx, st[x].mx + add);
		p = mn == (st[x].mn + add);
		return;
	}
	add += st[x].ps;
	int ls = x << 1;
	if (max(mx, st[ls ^ 1].mx + add) - min(mn, st[ls ^ 1].mn + add) >= w) { // idziemy w prawo
		suf(ls ^ 1, w, add);
	}
	else {
		mx = max(mx, st[ls ^ 1].mx + add);
		mn = min(mn, st[ls ^ 1].mn + add);
		suf(ls, w, add);
	}
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = c.size();
	q = l.size();
	com = 1;
	while (com < q + 1) {
		com <<= 1;
	}
	st.resize(com << 1);
	vector<pair<int, int>> z[n + 1];
	for (int i = 0; i < q; ++i) {
		z[l[i]].push_back({i + 1, v[i]});
		z[r[i] + 1].push_back({i + 1, -v[i]});
	}
	vector<int> odp(n);
	for (int i = 0; i < n; ++i) {
		for (auto j : z[i]) {
			all += j.second;
			ins(1, 0, com - 1, j.first, com, j.second);
		}
		mn = 1e18;
		mx = -1e18;
		p = 0;
		suf(1, c[i], 0);
		//~ printf("I = %d | %lld | %d | %lld %lld\n", i, all, p, mn, mx);
		if (p) {
			odp[i] = all + c[i] - mx;
		}
		else {
			odp[i] = all - mn;
		}
	}
	return odp;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 36164 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 332 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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