oj.uz

Submission #435145

# Submission time Handle Problem Language Result Execution time Memory
435145 2021-06-23T04:00:08 Z Kevin_Zhang_TW Distributing Candies (IOI21_candies) C++17
100 / 100
 1758 ms 31940 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "candies.h"

const int MAX_N = 200010;
const ll inf = 1ll << 59;

int n, m;
struct node {
	ll mx, mn, at;
	void operator += (ll v) { mx += v, mn += v, at += v; }
	node (ll a, ll b) : mx(a), mn(b), at(0) {}
	node (ll v) : at(0), mx(v), mn(v) {}
	node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
	node () : mx(0), mn(0), at(0) {}
	bool valid(int c) { return mx - mn <= c; }
};

vector<pair<ll,ll>> op[MAX_N];

struct sgt {
	int n;
	vector<node> val;
	sgt(int n) : n(n) {
		val.resize(n<<1);
	}
	void push(int i) {
		if (i >= n) return;
		val[i<<1] += val[i].at;
		val[i<<1|1] += val[i].at;
		val[i].at = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	void add(int l, int r, ll v) {
		l += n, r += n;
		int sl = l, sr = r;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;)
			upd(sl), upd(sr);
	}
	node qry(int l, int r) {
		l += n, r += n;
		for (int i = 18;i > 0;--i) push(l>>i), push(r>>i);
		node ret(-inf, inf);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) ret = node(ret, val[l++]);
			if (r&1) ret = node(ret, val[--r]);
		}
		return ret;
	}
}tree(0);

int qry(int c) {
	auto s0 = tree.qry(0, m);
	ll all = tree.qry(m-1, m).mx;
	if (s0.mx - s0.mn <= c) {
		return all - s0.mn;
	}
	int l = 0, r = m-1, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (tree.qry(mid, m).valid(c))
			r = mid;
		else
			l = mid+1;
	}
	assert(l > 0);
	ll v = tree.qry(l-1, l).mx;
	auto sl = tree.qry(l, m);
	if (sl.mx > v + c) {
		return c + (all - sl.mx);
	}
	else return all - sl.mn;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = c.size(), m = l.size();
	for (int i = 0;i < m;++i) {
		op[l[i]].pb(i+1, v[i]);
		op[r[i]+1].pb(i+1, -v[i]);
	}
	++m;
	tree = sgt(m);
	vector<int> res(n);
	for (int i = 0;i < n;++i) {
		for (auto [j, w] : op[i]) 
			tree.add(j, m, w);
		res[i] = qry(c[i]);
	}
	return res;
}

Compilation message

candies.cpp: In constructor 'node::node(ll)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
   24 |  ll mx, mn, at;
      |             ^~
candies.cpp:24:5: warning:   'll node::mx' [-Wreorder]
   24 |  ll mx, mn, at;
      |     ^~
candies.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  node (ll v) : at(0), mx(v), mn(v) {}
      |  ^~~~
candies.cpp: In constructor 'node::node(node, node)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
   24 |  ll mx, mn, at;
      |             ^~
candies.cpp:24:5: warning:   'll node::mx' [-Wreorder]
   24 |  ll mx, mn, at;
      |     ^~
candies.cpp:28:2: warning:   when initialized here [-Wreorder]
   28 |  node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
      |  ^~~~
candies.cpp: In function 'int qry(int)':
candies.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   mid = l + r >> 1;
      |         ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 8 ms 5144 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 12 ms 5260 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1595 ms 31884 KB Output is correct
2 Correct 1577 ms 31904 KB Output is correct
3 Correct 1455 ms 31888 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 351 ms 27956 KB Output is correct
3 Correct 654 ms 8740 KB Output is correct
4 Correct 1618 ms 31908 KB Output is correct
5 Correct 1758 ms 31904 KB Output is correct
6 Correct 1695 ms 31908 KB Output is correct
7 Correct 1496 ms 31904 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 152 ms 25416 KB Output is correct
4 Correct 529 ms 7796 KB Output is correct
5 Correct 996 ms 27740 KB Output is correct
6 Correct 1004 ms 27752 KB Output is correct
7 Correct 1165 ms 27720 KB Output is correct
8 Correct 884 ms 27720 KB Output is correct
9 Correct 1286 ms 27716 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 8 ms 5144 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 12 ms 5260 KB Output is correct
6 Correct 1595 ms 31884 KB Output is correct
7 Correct 1577 ms 31904 KB Output is correct
8 Correct 1455 ms 31888 KB Output is correct
9 Correct 5 ms 4940 KB Output is correct
10 Correct 351 ms 27956 KB Output is correct
11 Correct 654 ms 8740 KB Output is correct
12 Correct 1618 ms 31908 KB Output is correct
13 Correct 1758 ms 31904 KB Output is correct
14 Correct 1695 ms 31908 KB Output is correct
15 Correct 1496 ms 31904 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 5 ms 4940 KB Output is correct
18 Correct 152 ms 25416 KB Output is correct
19 Correct 529 ms 7796 KB Output is correct
20 Correct 996 ms 27740 KB Output is correct
21 Correct 1004 ms 27752 KB Output is correct
22 Correct 1165 ms 27720 KB Output is correct
23 Correct 884 ms 27720 KB Output is correct
24 Correct 1286 ms 27716 KB Output is correct
25 Correct 4 ms 4940 KB Output is correct
26 Correct 376 ms 7604 KB Output is correct
27 Correct 391 ms 27972 KB Output is correct
28 Correct 1163 ms 31924 KB Output is correct
29 Correct 1318 ms 31888 KB Output is correct
30 Correct 1365 ms 31940 KB Output is correct
31 Correct 1525 ms 31896 KB Output is correct
32 Correct 1447 ms 31888 KB Output is correct