#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1234567890
#define ll long long
ll last = 0;
pair<ll, ll> seg[530000];
ll lazy[530000];
pair<ll, ll> Merge(pair<ll, ll> l, pair<ll, ll> r)
{
return {min(l.first,r.first), max(l.second, r.second)};
}
void Propagate(int n, int l, int r) // add
{
if (lazy[n])
{
if (l != r)
{
lazy[n<<1] += lazy[n];
lazy[n<<1|1] += lazy[n];
}
seg[n].first += lazy[n];
seg[n].second += lazy[n];
lazy[n] = 0;
}
}
pair<ll, ll> Update(int L, int R, ll val, int n, int l, int r)
{
Propagate(n, l, r);
if (r < L || R < l) return seg[n];
if (L <= l && r <= R)
{
lazy[n] += val; // add
Propagate(n, l, r);
return seg[n];
}
int mid = l+r>>1;
return seg[n] = Merge(Update(L, R, val, n<<1, l, mid), Update(L, R, val, n<<1|1, mid+1, r));
}
ll Kth(ll C, ll mn, ll mx, int n, int l, int r) // 1 <= k <= propagated_seg[1]
{
Propagate(n, l, r); //
if (l == r)
{
mn = min(mn, seg[n].first);
mx = max(mx, seg[n].second);
assert(mx - mn >= C);
if (mn == seg[n].first) return C - (mx - last);
else return last - mn;
}
int mid = l+r>>1;
Propagate(n<<1|1, mid+1, r);
ll next_mn = min(mn, seg[n<<1|1].first), next_mx = max(mx, seg[n<<1|1].second);
if (next_mx - next_mn >= C) return Kth(C, mn, mx, n<<1|1, mid+1, r);
return Kth(C, next_mn, next_mx, n<<1, l, mid);
}
int N, Q;
vector<pair<int, int> > D[200201];
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
N = C.size(); Q = L.size();
// INF와 0을 맨 앞에 끼워넣어서 예외 처리
D[0].push_back({0, INF});
D[0].push_back({1, -INF});
for(int i=0; i<Q; i++)
{
D[L[i]].push_back({i+2, V[i]});
D[R[i]+1].push_back({i+2, -V[i]});
}
vector<int> res(N);
for(int i=0; i<N; i++)
{
for(auto [idx,val] : D[i])
{
last += val;
Update(idx, Q+1, val, 1, 0, Q+1); //
}
res[i] = Kth(C[i], (ll)1e18, (ll)-1e18, 1, 0, Q+1);
}
return res;
}
// int main() {}
Compilation message
candies.cpp: In function 'std::pair<long long int, long long int> Update(int, int, long long int, int, int, int)':
candies.cpp:40:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l+r>>1;
| ~^~
candies.cpp: In function 'long long int Kth(long long int, long long int, long long int, int, int, int)':
candies.cpp:54:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = l+r>>1;
| ~^~
# |
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 |
6 ms |
5196 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
7 ms |
5196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
676 ms |
31304 KB |
Output is correct |
2 |
Correct |
663 ms |
31532 KB |
Output is correct |
3 |
Correct |
626 ms |
31392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
377 ms |
26520 KB |
Output is correct |
3 |
Correct |
87 ms |
8756 KB |
Output is correct |
4 |
Correct |
592 ms |
31400 KB |
Output is correct |
5 |
Correct |
640 ms |
31400 KB |
Output is correct |
6 |
Correct |
685 ms |
31300 KB |
Output is correct |
7 |
Correct |
687 ms |
31428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4940 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
153 ms |
25228 KB |
Output is correct |
4 |
Correct |
82 ms |
7568 KB |
Output is correct |
5 |
Correct |
271 ms |
27392 KB |
Output is correct |
6 |
Correct |
252 ms |
27500 KB |
Output is correct |
7 |
Correct |
252 ms |
27564 KB |
Output is correct |
8 |
Correct |
237 ms |
27396 KB |
Output is correct |
9 |
Correct |
244 ms |
27560 KB |
Output is correct |
# |
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 |
6 ms |
5196 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
7 ms |
5196 KB |
Output is correct |
6 |
Correct |
676 ms |
31304 KB |
Output is correct |
7 |
Correct |
663 ms |
31532 KB |
Output is correct |
8 |
Correct |
626 ms |
31392 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
377 ms |
26520 KB |
Output is correct |
11 |
Correct |
87 ms |
8756 KB |
Output is correct |
12 |
Correct |
592 ms |
31400 KB |
Output is correct |
13 |
Correct |
640 ms |
31400 KB |
Output is correct |
14 |
Correct |
685 ms |
31300 KB |
Output is correct |
15 |
Correct |
687 ms |
31428 KB |
Output is correct |
16 |
Correct |
5 ms |
4940 KB |
Output is correct |
17 |
Correct |
5 ms |
4940 KB |
Output is correct |
18 |
Correct |
153 ms |
25228 KB |
Output is correct |
19 |
Correct |
82 ms |
7568 KB |
Output is correct |
20 |
Correct |
271 ms |
27392 KB |
Output is correct |
21 |
Correct |
252 ms |
27500 KB |
Output is correct |
22 |
Correct |
252 ms |
27564 KB |
Output is correct |
23 |
Correct |
237 ms |
27396 KB |
Output is correct |
24 |
Correct |
244 ms |
27560 KB |
Output is correct |
25 |
Correct |
4 ms |
4940 KB |
Output is correct |
26 |
Correct |
82 ms |
7624 KB |
Output is correct |
27 |
Correct |
382 ms |
26564 KB |
Output is correct |
28 |
Correct |
605 ms |
31408 KB |
Output is correct |
29 |
Correct |
652 ms |
31300 KB |
Output is correct |
30 |
Correct |
610 ms |
31468 KB |
Output is correct |
31 |
Correct |
642 ms |
31552 KB |
Output is correct |
32 |
Correct |
635 ms |
31392 KB |
Output is correct |