#include "candies.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct segTree{
int l, r;
segTree *tl, *tr;
ll ss, mn, mx;
segTree(int l, int r) : l(l), r(r){
ss = mn = mx = 0;
if(l != r){
int mid = l + (r - l) / 2;
tl = new segTree(l, mid);
tr = new segTree(mid + 1, r);
}
}
void add(int x, ll y){
if(x < l || r < x) return;
if(l == r) return (void)(ss += y, mn += y, mx += y);
tl->add(x, y), tr->add(x, y);
ss = tl->ss + tr->ss;
mn = min(tl->mn + tr->ss, tr->mn);
mx = max(tl->mx + tr->ss, tr->mx);
}
ll qry(ll x){
if(l == r) return ss;
return tr->mx < x ? min(tl->qry(x - tr->ss) + tr->ss, tr->mn) : tr->qry(x);
}
};
const int mxn = 200001;
int n, q;
vi b[mxn];
vi distribute_candies(vi a, vi l, vi r, vi v){
n = a.size(), q = l.size();
for(int i = 0; i < q; i++){
b[l[i]].push_back(i + 1);
b[r[i] + 1].push_back(-i - 1);
}
vi f(n);
segTree tre(-2, q - 1);
tre.add(-2, inf), tre.add(-1, -inf);
for(int i = 0; i < n; i++){
for(int j : b[i]) tre.add(abs(j) - 1, j / abs(j) * v[abs(j) - 1]);
int l = -1, r = a[i];
while(r - l > 1){
int mid = (l + r) / 2;
if(mid - tre.qry(mid) < a[i]) l = mid;
else r = mid;
}
f[i] = r;
}
return f;
}
/*int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vi a(n), l(q), r(q), v(q);
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];
vi f = distribute_candies(a, l, r, v);
cout << f[0];
for(int i = 1; i < n; i++) cout << " " << f[i];
cout << endl;
return 0;
}*/
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:34:17: warning: 'tre.segTree::tr' may be used uninitialized in this function [-Wmaybe-uninitialized]
34 | ss = tl->ss + tr->ss;
| ^~
candies.cpp:57:10: note: 'tre.segTree::tr' was declared here
57 | segTree tre(-2, q - 1);
| ^~~
candies.cpp:34:17: warning: 'tre.segTree::tl' may be used uninitialized in this function [-Wmaybe-uninitialized]
34 | ss = tl->ss + tr->ss;
| ^~
candies.cpp:57:10: note: 'tre.segTree::tl' was declared here
57 | segTree tre(-2, q - 1);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
960 ms |
47600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
