oj.uz

Submission #446125

# Submission time Handle Problem Language Result Execution time Memory
446125 2021-07-21T02:52:40 Z dennisstar Distributing Candies (IOI21_candies) C++17
100 / 100
 508 ms 37016 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MX = 1<<19;

vector<ll> smx(MX), smn(MX), st(MX);

void upd(int i, int s, int e, int t, ll v) {
	if (s==e) {
		smx[i]=max(0ll, v);
		smn[i]=min(0ll, v);
		st[i]=v;
		return ;
	}

	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, v);
	else upd(i*2+1, m+1, e, t, v);
	
	st[i]=st[i*2]+st[i*2+1];
	smx[i]=max(smx[i*2], st[i*2]+smx[i*2+1]);
	smn[i]=min(smn[i*2], st[i*2]+smn[i*2+1]);
}

ll get(int i, int s, int e, ll c) {
	if (s==e) return min(max(st[i], 0ll), c);

	int m=(s+e)/2;
	if (smx[i*2+1]-smn[i*2+1]>c) return get(i*2+1, m+1, e, c);

	ll r=get(i*2, s, m, c);
	if (r+smx[i*2+1]>c) return c-(smx[i*2+1]-st[i*2+1]);
	if (r+smn[i*2+1]<0) return st[i*2+1]-smn[i*2+1];
	return r+st[i*2+1];
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int N=c.size(), Q=l.size();
	vector<int> rt;

	vector<vector<int>> q(N+1);
	for (int i=0; i<Q; i++) q[l[i]].emplace_back(i+1), q[r[i]+1].emplace_back(-(i+1));
	for (int i=0; i<N; i++) {
		for (auto &j:q[i]) {
			if (j>0) j--, upd(1, 0, Q-1, j, v[j]);
			else j=-j-1, upd(1, 0, Q-1, j, 0);
		}
		rt.emplace_back(get(1, 0, Q-1, c[i]));
	}

	return rt;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 7 ms 12520 KB Output is correct
3 Correct 8 ms 12644 KB Output is correct
4 Correct 8 ms 12644 KB Output is correct
5 Correct 10 ms 12772 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 35092 KB Output is correct
2 Correct 478 ms 34480 KB Output is correct
3 Correct 453 ms 34224 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 298 ms 22668 KB Output is correct
3 Correct 87 ms 22280 KB Output is correct
4 Correct 459 ms 36280 KB Output is correct
5 Correct 460 ms 36668 KB Output is correct
6 Correct 466 ms 37016 KB Output is correct
7 Correct 477 ms 36412 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12620 KB Output is correct
2 Correct 7 ms 12624 KB Output is correct
3 Correct 130 ms 21724 KB Output is correct
4 Correct 81 ms 21196 KB Output is correct
5 Correct 206 ms 30256 KB Output is correct
6 Correct 208 ms 31108 KB Output is correct
7 Correct 208 ms 31412 KB Output is correct
8 Correct 210 ms 30136 KB Output is correct
9 Correct 221 ms 31540 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 7 ms 12520 KB Output is correct
3 Correct 8 ms 12644 KB Output is correct
4 Correct 8 ms 12644 KB Output is correct
5 Correct 10 ms 12772 KB Output is correct
6 Correct 467 ms 35092 KB Output is correct
7 Correct 478 ms 34480 KB Output is correct
8 Correct 453 ms 34224 KB Output is correct
9 Correct 7 ms 12620 KB Output is correct
10 Correct 298 ms 22668 KB Output is correct
11 Correct 87 ms 22280 KB Output is correct
12 Correct 459 ms 36280 KB Output is correct
13 Correct 460 ms 36668 KB Output is correct
14 Correct 466 ms 37016 KB Output is correct
15 Correct 477 ms 36412 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 7 ms 12624 KB Output is correct
18 Correct 130 ms 21724 KB Output is correct
19 Correct 81 ms 21196 KB Output is correct
20 Correct 206 ms 30256 KB Output is correct
21 Correct 208 ms 31108 KB Output is correct
22 Correct 208 ms 31412 KB Output is correct
23 Correct 210 ms 30136 KB Output is correct
24 Correct 221 ms 31540 KB Output is correct
25 Correct 7 ms 12620 KB Output is correct
26 Correct 83 ms 21316 KB Output is correct
27 Correct 273 ms 22380 KB Output is correct
28 Correct 508 ms 34804 KB Output is correct
29 Correct 494 ms 35300 KB Output is correct
30 Correct 473 ms 35544 KB Output is correct
31 Correct 445 ms 35568 KB Output is correct
32 Correct 455 ms 35816 KB Output is correct