#include <iostream>
#include "candies.h"
#include <cassert>
#include <cstdio>
#include <climits>
#include <vector>
using namespace std;
class segtree{
public:
struct node{
long long mini;
long long maxi;
long long lazy;
};
vector<node> tree;
int N;
void init(int n){
N = 1;
while(N <= n){
N*=2;
}
tree.assign(2 * N, {0, 0, 0});
}
void lazy_upd(int head){
tree[head].mini += tree[head].lazy;
tree[head].maxi += tree[head].lazy;
if(head < N){
tree[head * 2 + 1].lazy += tree[head].lazy;
tree[head * 2 + 2].lazy += tree[head].lazy;
}
tree[head].lazy = 0;
}
void update(int head, int L, int R, int l, int r, int val){
lazy_upd(head);
if(l <= L && R <= r){
tree[head].lazy = val;
lazy_upd(head);
return;
}
if(R <= l || r <= L){
return;
}
int mid = (L + R) / 2;
update(head * 2 + 1, L, mid, l, r, val);
update(head * 2 + 2, mid, R, l, r, val);
tree[head].mini = min(tree[head * 2 + 1].mini, tree[head * 2 + 2].mini);
tree[head].maxi = max(tree[head * 2 + 1].maxi, tree[head * 2 + 2].maxi);
}
void update(int l, int val){
update(0, 0, N, l, N, val);
}
long long getmin(int head, int L, int R, int l, int r){
lazy_upd(head);
if(l <= L && R <= r){
return tree[head].mini;
}
if(R <= l || r <= L){
return LLONG_MAX;
}
int mid = (L + R)/ 2;
return min(getmin(head * 2 + 1, L, mid, l, r), getmin(head * 2 + 2, mid, R, l, r));
}
long long getmin(int l){
return getmin(0, 0, N, l, N);
}
long long getmax(int head, int L, int R, int l, int r){
lazy_upd(head);
if(l <= L && R <= r){
return tree[head].maxi;
}
if(R <= l || r <= L){
return LLONG_MIN;
}
int mid = (L + R)/ 2;
return max(getmax(head * 2 + 1, L, mid, l, r), getmax(head * 2 + 2, mid, R, l, r));
}
long long getmax(int l){
return getmax(0, 0, N, l, N);
}
long long getpoint(int head, int L, int R, int x){
lazy_upd(head);
if(R - L == 1){
return tree[head].mini;
}
int mid = (L + R) / 2;
if(x < mid){
return getpoint(head * 2 + 1, L, mid, x);
}
else{
return getpoint(head * 2 + 2, mid, R, x);
}
}
long long getpoint(int x){
return getpoint(0, 0, N, x);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> val){
int N = c.size();
int Q = l.size();
vector<int> ans(N);
segtree tree;
tree.init(Q + 5);
vector<vector<pair<int, int>>> op(N + 5);
for(int i = 0; i < Q; i ++){
op[l[i]].push_back({i + 2, val[i]});
op[r[i]+1].push_back({i + 2, -val[i]});
}
for(int i = 0; i < N; i ++){
for(auto[ll, rr] : op[i]){
tree.update(ll, rr);
}
int l = 0, r = Q + 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(tree.getmax(mid)-tree.getmin(mid) > c[i]){
l = mid;
}
else{
r = mid;
}
}
//cout << tree.getpoint(l) << " " << tree.getpoint(Q + 1) << " " << l << endl;
long long a = tree.getpoint(l), b = tree.getpoint(Q + 1);
if(a < b){
int d = tree.getmax(l);
ans[i] = c[i] - (d - b);
}
else{
int d = tree.getmin(l);
ans[i] = b - d;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1327 ms |
31456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
