#include"bits/stdc++.h"
// #define int long long
#define endl '\n'
using namespace std;
long long N, Left, Right, Value;
long long seg[2000001], lazy1[2000001], lazy2[2000001], pref[200001]; // lazy2[i] = 1 ? max : 0
#define sum(l,r) (r>0 ? pref[r-1] : 0) - (l>1 ? pref[l-2] : 0)
void Spread2 (int l, int r, int ind) {
if (l != r) {
lazy1[ind * 2] += lazy1[ind];
lazy1[ind * 2 + 1] += lazy1[ind];
int mid = (l + r) / 2;
seg[ind * 2] += (mid - l + 1) * lazy1[ind];
seg[ind * 2 + 1] += (r - mid) * lazy1[ind];
}
lazy1[ind] = 0;
}
void Spread1 (int l, int r, int ind) {
if (lazy2[ind] == 1 and l != r) {
lazy2[ind * 2] = 1;
lazy2[ind * 2 + 1] = 1;
lazy1[ind * 2] = 0;
lazy1[ind * 2 + 1] = 0;
int mid = (l + r) / 2;
seg[ind * 2] = sum(l, mid);
seg[ind * 2 + 1] = sum(mid + 1, r);
}
else if (lazy2[ind] == -1 and l != r) {
lazy2[ind * 2] = -1;
lazy2[ind * 2 + 1] = -1;
lazy1[ind * 2] = 0;
lazy1[ind * 2 + 1] = 0;
seg[ind * 2] = 0;
seg[ind * 2 + 1] = 0;
}
lazy2[ind] = 0;
}
int Query (int l = 1, int r = N, int ind = 1) {
if (l > Right || r < Left) return 0;
Spread1(l, r, ind);
Spread2(l, r, ind);
if (l >= Left and r <= Right) return seg[ind];
int mid = (l + r) / 2;
return Query(l, mid, ind * 2) + Query(mid + 1, r, ind * 2 + 1);
}
void Update (int l = 1, int r = N, int ind = 1) {
if (l > Right || r < Left) return;
Spread1(l, r, ind);
Spread2(l, r, ind);
if (l >= Left and r <= Right) {
if (Value == 2000000000000000000) { // max
lazy2[ind] = 1;
seg[ind] = sum(l, r);
} else if (Value == 2000000000000000000 - 1) { // 0
lazy2[ind] = -1;
seg[ind] = 0;
} else { // add
lazy1[ind] += Value;
seg[ind] += (r - l + 1) * Value;
}
return;
}
int mid = (l + r) / 2;
Update(l, mid, ind * 2);
Update(mid + 1, r, ind * 2 + 1);
seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
}
vector<int> distribute_candies (vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
N = exp2(ceil(log2(n)));
bool st1 = (n <= 2000 and q <= 2000);
bool st2 = 1; for (int i = 0 ; i < q ; i++) if (v[i] < 0) st2 = 0;
bool st3 = 1; for (int i = 0 ; i < q ; i++) if (l[i] != 0 || r[i] != n - 1) st3 = 0;
// st1 = st2 = 0;
if (st1) {
vector<int> ret(n, 0);
for (int i = 0 ; i < q ; i++) {
for (int j = l[i] ; j <= r[i] ; j++) {
ret[j] = max(0, min(c[j], ret[j] + v[i]));
}
}
return ret;
}
if (st2) {
vector<int> ret(n, 0);
// vector<long long> pref(n + 1, 0);
for (int i = 0 ; i < q ; i++) {
pref[l[i]] += v[i];
pref[r[i] + 1] -= v[i];
}
for (int i = 1 ; i < n ; i++) pref[i] += pref[i-1];
for (int i = 0 ; i < n ; i++) ret[i] = min((long long)c[i], pref[i]);
return ret;
}
if (st3) {
vector<int> ans(n);
vector<pair<int,int>> srt;
for (int i = 0 ; i < n ; i++) srt.emplace_back(c[i], i);
sort(srt.begin(), srt.end());
for (int i = 0 ; i < n ; i++) {
pref[i] = srt[i].first + (i ? pref[i-1] : 0);
}
for (int i = 0 ; i < q ; i++) {
int l = 0, r = n;
Left = Right = 1;
bool _F = (v[i] < 0 ? Query() + v[i] <= 0 : Query() + v[i] >= c[0]);
while (r - l > 1) {
int mid = (l + r) / 2;
Left = Right = mid + 1;
int val = Query();
// cerr << mid + 1 << " " << val << " " << c[srt[mid].second] << " " << v[i] << endl;
if (v[i] < 0) {
if (val + v[i] <= 0) {l = mid;}
else r = mid;
} else {
if (val + v[i] >= c[srt[mid].second]) {l = mid;}
else r = mid;
}
}
if (_F) {
Left = 1, Right = l+1;
// cerr << "1: " << Left << " " << Right << endl;
Value = 2000000000000000000;
if (v[i] < 0) Value--;
// cerr << Value << " " << v[i] << endl;
Update();
}
if (!_F or (_F and l < (n - 1))) {
if (!_F) Left = 1;
else Left = l+2;
Right = n;
// cerr << "2: " << Left << " " << Right << endl;
Value = v[i];
Update();
}
}
vector<int> ret(n);
for (int i = 0 ; i < n ; i++) {
Left = Right = i + 1;
ret[srt[i].second] = max(0, min(c[srt[i].second], Query()));
}
return ret;
}
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:152:1: warning: control reaches end of non-void function [-Wreturn-type]
152 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
8892 KB |
Output is correct |
| 2 |
Correct |
117 ms |
8900 KB |
Output is correct |
| 3 |
Correct |
121 ms |
8808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
480 ms |
5100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
497 ms |
5232 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
169 ms |
8892 KB |
Output is correct |
| 7 |
Correct |
117 ms |
8900 KB |
Output is correct |
| 8 |
Correct |
121 ms |
8808 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Incorrect |
480 ms |
5100 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
