oj.uz

Submission #1106308

# Submission time Handle Problem Language Result Execution time Memory
1106308 2024-10-29T20:57:41 Z pit4h Distributing Candies (IOI21_candies) C++17
100 / 100
 3177 ms 161872 KB 
#include "candies.h"

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
using vi=vector<int>;
#define mp make_pair
#define eb emplace_back
#define x first
#define y second
#define sz(x)int((x).size())
#define all(x)(x).begin(),(x).end()
#define rep(i,a,b)for(int i=(a);i<(b);i++)
#define per(i,a,b)for(int i=(b)-1;i>=(a);i--)
bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
#ifdef LOCAL
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.x<<", "<<p.y<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto&e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define debug(...){}
#endif

const int MAXN = 2e5 + 5, MAXQ = 2e5 + 5, base = (1 << 18);

const ll INF = 1e18;

vi c, cnt;

int n, q;

vector<pair<ll, int>> tree[2 * base + 1];

void ins(int l, int r, pair<ll, int> val) {
	l += base;
	r += base;
	tree[l].eb(val);
	if (l != r) {
		tree[r].eb(val);
	}
	while (l / 2 != r / 2) {
		if (l % 2 == 0) {
			tree[l+1].eb(val);
		}
		if (r % 2 == 1) {
			tree[r-1].eb(val);
		}
		l /= 2;
		r /= 2;
	}
}

struct Solver {
	ll pref[2*base], lazy[2*base], tree_min[2*base], tree_max[2*base];
	ll total;
	void init(int siz) {
		total=0;
		rep(i,0,2*base) {
			pref[i] = lazy[i] = 0;
			tree_min[i] = 0;
			tree_max[i] = 0;
		}
	}
	void ins(int i, ll v) {
		total += v;
		add(1, i, v);
	}
	ll get(ll cap) {
		auto [ceil, sub] = rec(cap);	
		debug(ceil, sub, total);
		if (ceil == -1) {
			return total - tree_min[1];
		}
		return total - sub + cap * ceil;
	}
	void push(int id, ll v) {
		pref[id] += v;
		lazy[id] += v;
		tree_min[id] += v;
		tree_max[id] += v;
	}
	void add(int id, int i, ll v, int rl=0, int rr=base-1) {
		if (rr < i) return;
		if (rl >= i) {
			push(id, v);
			return;
		}

		push(id*2,lazy[id]);
		push(id*2+1,lazy[id]);
		lazy[id]=0;

		int mid = (rl+rr)/2;
		add(id*2,i,v,rl,mid);
		add(id*2+1,i,v,mid+1,rr);

		tree_min[id] = min(tree_min[id*2], tree_min[id*2+1]);
		tree_max[id] = max(tree_max[id*2], tree_max[id*2+1]);
	}

	pair<int,ll> rec(ll cap, int id=1, int rl=0,  int rr=base-1, ll suf_min=INF, ll suf_max=-INF) {
		debug("rec", cap, id, rl, rr, suf_min, suf_max, tree_min[id], tree_max[id]);
		if (max(suf_max, tree_max[id]) - min(suf_min, tree_min[id]) < cap) {
			return mp(-1,0LL);	
		}
		if (rl == rr) {
			if (suf_max - pref[id] >= cap) {
				return mp(1,suf_max);
			}
			else {
				assert(pref[id] - suf_min >= cap);
				return mp(0,suf_min);
			}
		}

		push(id*2,lazy[id]);
		push(id*2+1,lazy[id]);
		lazy[id]=0;

		int mid=(rl+rr)/2;
		pair<int,ll> res = rec(cap, id*2+1, mid+1, rr, suf_min, suf_max);
		if (res != mp(-1,0LL)) {
			return res;
		}
		ll new_min = min(suf_min, tree_min[id*2+1]), new_max = max(suf_max, tree_max[id*2+1]);
		return rec(cap, id*2, rl, mid, new_min, new_max);
	}
} solver;

void solve(int id, int l, int r) {
	debug(id, l, r);

	for (auto& [v, i]: tree[id]) {
		debug("ins", i, v);
		solver.ins(i, v);	
	}

	if (l == r) {
		if (l < n) {
			cnt[l] = solver.get(c[l]);
		}
	}
	else {
		int mid = (l+r)/2;
		solve(id * 2, l, mid);
		solve(id * 2 + 1, mid + 1, r);
	}

	for (auto& [v, i]: tree[id]) {
		solver.ins(i, -v);
	}
}

vector<int> distribute_candies(vector<int> _c, vector<int> l,
                               vector<int> r, vector<int> v) {
	c = _c;
    n = c.size(); q = sz(l);
    vector<int> s(n);
	cnt.resize(n); rep(i,0,n) cnt[i] = 0;

	rep(i,0,q) {
		debug("INS", l[i], r[i], v[i], i);
		ins(l[i], r[i], mp(v[i], i+1));
	}

	solver.init(q);
	solve(1, 0, base - 1);

	rep(i,0,n) s[i] = cnt[i];
    return s;
}

Compilation message

candies.cpp:16:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
      |            ^~~~
candies.cpp:16:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
      |                   ^~~~
candies.cpp:17:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
      |            ^~~~
candies.cpp:17:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
      |                   ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29008 KB Output is correct
2 Correct 7 ms 29008 KB Output is correct
3 Correct 13 ms 29264 KB Output is correct
4 Correct 22 ms 29592 KB Output is correct
5 Correct 27 ms 30032 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2450 ms 117528 KB Output is correct
2 Correct 2657 ms 116944 KB Output is correct
3 Correct 2590 ms 116748 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29008 KB Output is correct
2 Correct 1412 ms 83304 KB Output is correct
3 Correct 194 ms 37176 KB Output is correct
4 Correct 2454 ms 118932 KB Output is correct
5 Correct 2591 ms 119212 KB Output is correct
6 Correct 2522 ms 119648 KB Output is correct
7 Correct 2451 ms 118932 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29008 KB Output is correct
2 Correct 8 ms 29008 KB Output is correct
3 Correct 2114 ms 116148 KB Output is correct
4 Correct 122 ms 35384 KB Output is correct
5 Correct 3096 ms 160500 KB Output is correct
6 Correct 3067 ms 161256 KB Output is correct
7 Correct 3098 ms 161760 KB Output is correct
8 Correct 2997 ms 160552 KB Output is correct
9 Correct 3177 ms 161872 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29008 KB Output is correct
2 Correct 7 ms 29008 KB Output is correct
3 Correct 13 ms 29264 KB Output is correct
4 Correct 22 ms 29592 KB Output is correct
5 Correct 27 ms 30032 KB Output is correct
6 Correct 2450 ms 117528 KB Output is correct
7 Correct 2657 ms 116944 KB Output is correct
8 Correct 2590 ms 116748 KB Output is correct
9 Correct 8 ms 29008 KB Output is correct
10 Correct 1412 ms 83304 KB Output is correct
11 Correct 194 ms 37176 KB Output is correct
12 Correct 2454 ms 118932 KB Output is correct
13 Correct 2591 ms 119212 KB Output is correct
14 Correct 2522 ms 119648 KB Output is correct
15 Correct 2451 ms 118932 KB Output is correct
16 Correct 7 ms 29008 KB Output is correct
17 Correct 8 ms 29008 KB Output is correct
18 Correct 2114 ms 116148 KB Output is correct
19 Correct 122 ms 35384 KB Output is correct
20 Correct 3096 ms 160500 KB Output is correct
21 Correct 3067 ms 161256 KB Output is correct
22 Correct 3098 ms 161760 KB Output is correct
23 Correct 2997 ms 160552 KB Output is correct
24 Correct 3177 ms 161872 KB Output is correct
25 Correct 7 ms 29008 KB Output is correct
26 Correct 96 ms 35152 KB Output is correct
27 Correct 1399 ms 84040 KB Output is correct
28 Correct 2393 ms 117444 KB Output is correct
29 Correct 2509 ms 118020 KB Output is correct
30 Correct 2591 ms 117792 KB Output is correct
31 Correct 2409 ms 118204 KB Output is correct
32 Correct 2368 ms 118316 KB Output is correct