oj.uz

Submission #777342

# Submission time Handle Problem Language Result Execution time Memory
777342 2023-07-09T06:18:18 Z Trisanu_Das Distributing Candies (IOI21_candies) C++17
100 / 100
 354 ms 37028 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 4 ms 12628 KB Output is correct
2 Correct 5 ms 12628 KB Output is correct
3 Correct 5 ms 12628 KB Output is correct
4 Correct 5 ms 12652 KB Output is correct
5 Correct 6 ms 12776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 35104 KB Output is correct
2 Correct 263 ms 34328 KB Output is correct
3 Correct 262 ms 34188 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12564 KB Output is correct
2 Correct 163 ms 22676 KB Output is correct
3 Correct 52 ms 22340 KB Output is correct
4 Correct 339 ms 36168 KB Output is correct
5 Correct 337 ms 36616 KB Output is correct
6 Correct 288 ms 37028 KB Output is correct
7 Correct 277 ms 36292 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12644 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 81 ms 21784 KB Output is correct
4 Correct 50 ms 21268 KB Output is correct
5 Correct 127 ms 30184 KB Output is correct
6 Correct 133 ms 30788 KB Output is correct
7 Correct 130 ms 31148 KB Output is correct
8 Correct 129 ms 30024 KB Output is correct
9 Correct 131 ms 31156 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12628 KB Output is correct
2 Correct 5 ms 12628 KB Output is correct
3 Correct 5 ms 12628 KB Output is correct
4 Correct 5 ms 12652 KB Output is correct
5 Correct 6 ms 12776 KB Output is correct
6 Correct 354 ms 35104 KB Output is correct
7 Correct 263 ms 34328 KB Output is correct
8 Correct 262 ms 34188 KB Output is correct
9 Correct 5 ms 12564 KB Output is correct
10 Correct 163 ms 22676 KB Output is correct
11 Correct 52 ms 22340 KB Output is correct
12 Correct 339 ms 36168 KB Output is correct
13 Correct 337 ms 36616 KB Output is correct
14 Correct 288 ms 37028 KB Output is correct
15 Correct 277 ms 36292 KB Output is correct
16 Correct 5 ms 12644 KB Output is correct
17 Correct 5 ms 12636 KB Output is correct
18 Correct 81 ms 21784 KB Output is correct
19 Correct 50 ms 21268 KB Output is correct
20 Correct 127 ms 30184 KB Output is correct
21 Correct 133 ms 30788 KB Output is correct
22 Correct 130 ms 31148 KB Output is correct
23 Correct 129 ms 30024 KB Output is correct
24 Correct 131 ms 31156 KB Output is correct
25 Correct 5 ms 12636 KB Output is correct
26 Correct 55 ms 21316 KB Output is correct
27 Correct 144 ms 22288 KB Output is correct
28 Correct 264 ms 34780 KB Output is correct
29 Correct 313 ms 35348 KB Output is correct
30 Correct 265 ms 35436 KB Output is correct
31 Correct 274 ms 35644 KB Output is correct
32 Correct 270 ms 35744 KB Output is correct