#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int j, n, m;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
n = c.size();
m = r.size();
// vector<vector<int>> L(n),R(n);
// for(int i=0; i < m;i++){
// L[l[i]].push_back(i);
// R[r[i]].push_back(i);
// }
// for(int i=0; i < n;i++){
// for(int x : L[i]) st.update(x, n, v[x]);
// }
vector<int> s(n);
vector<array<ll,3>> arr(m + 4, {0, ll(-1e18), ll(1e18)});
vector<ll> pre(m + 4);
arr[0] = {0,0,0};
// sum, maximum, minimum
for(int i=1; i <= m;i++){
arr[i+1][0] = v[i-1] + arr[i][0];
}
for(int i = m + 1; i >= 1;i--){
arr[i][1] = max(arr[i][0], arr[i+1][1]);
arr[i][2] = min(arr[i][0], arr[i+1][2]);
}
int limit = 1e18;
int tp;
for(int i = 1; i <= m;i++){
pre[i+1] = pre[i] + v[i-1];
if(limit > pre[i+1]){
tp = i + 1;
limit = pre[i+1];
}
}
// for(int i=1; i <= m + 1;i++) cout << arr[i][1] << ' '; cout << endl;
for(int i=0; i < n;i++){
int l = 0;
int r = m;
int id = -1;
while(l <= r){
int mid = (l+r)/2;
if(arr[mid + 1][1] - arr[mid + 1][2] >= c[i]){
l = mid+1;
id = mid;
} else r = mid-1;
}
if(id == -1){
s[i] = pre[m+1] - pre[tp];
continue;
}
int cond = 0;
id++;
if(arr[id][1] == arr[id+1][1]) cond = 1;
else cond = 0;
if(cond){
ll curr = arr[id][1];
int l = id - 1;
int r = m;
while(l <= r){
int mid = (l+r)/2;
if(arr[mid + 1][1] == curr){
id = mid;
l = mid + 1;
} else r = mid - 1;
}
id++;
s[i] = c[i] - (arr[id][0] - arr[m+1][0]);
} else{
ll curr = arr[id][2];
int l = id - 1;
int r = m;
while(l <= r){
int mid = (l+r)/2;
if(arr[mid + 1][2] == curr){
id = mid;
l = mid + 1;
} else r = mid - 1;
}
id++;
s[i] = arr[m+1][0] - arr[id][0];
}
}
return s;
}
// void solve(){
// cin >> n;
// vector<int> c(n);
// for(int i=0; i < n;i++) cin >> c[i];
// int q; cin >> q;
// vector<int> l(q),r(q),v(q);
// for(int i=0; i < q;i++) cin >> l[i];
// for(int i=0; i < q;i++) cin >> r[i];
// for(int i=0; i < q;i++) cin >> v[i];
// vector<int> ans = distribute_candies(c,l,r,v); cout << endl;
// for(int x : ans) cout << x << ' '; cout << endl;
// }
// int32_t main(){
// ios::sync_with_stdio(false);
// cin.tie();
// cout.tie();
// int t=1;
// // cin >> t;
// while(t--){
// // cout << t << ":\n";
// solve();
// }
// }
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:41:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
41 | int limit = 1e18;
| ^~~~
candies.cpp:66:37: warning: 'tp' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | s[i] = pre[m+1] - pre[tp];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
18548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
