#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
template <typename T>
ostream& operator << (ostream& os, const vector<T>& a) {
os << '[';
bool E = false;
for(const T& x : a) {
if(E) os << ' ';
os << x;
E = true;
}
return os << ']';
}
struct node{
ll l,r;
node *lft = NULL,*rght = NULL;
ll offset = 0, minimum = 0, maximum = 0;
//offset is already applied to min/max at this layer
node(ll ltemp, ll rtemp){
l=ltemp;r=rtemp;
}
};
void add(node *x, ll l, ll r, ll val) {
if (r <= x->l||x->r <= l) {
return;
}
if (l <= x->l&&x->r <= r) {
x->offset+=val;
x->minimum+=val;
x->maximum+=val;
return;
}
if (x->lft == NULL){
x->lft = new node(x->l,(x->l+x->r)/2);
}
if (x->rght == NULL){
x->rght = new node((x->l+x->r)/2,x->r);
}
add(x->lft,l,r,val);
add(x->rght,l,r,val);
x->minimum=min(x->lft->minimum,x->rght->minimum)+x->offset;
x->maximum=max(x->lft->maximum,x->rght->minimum)+x->offset;
}
ll findval(node *x, ll poll){
if (poll < x->l||x->r <= poll) {
return LLONG_MIN;
}
if (x->l+1==x->r) {
return x->offset;
}
if (x->lft == NULL){
x->lft = new node(x->l,(x->l+x->r)/2);
}
if (x->rght == NULL){
x->rght = new node((x->l+x->r)/2,x->r);
}
ll temp = findval(x->lft, poll);
if (temp == LLONG_MIN){
temp = findval(x->rght, poll);
}
return temp+x->offset;
}
pair<ll,ll> limitfind(node *x, ll l, ll r){
if (r <= x->l||x->r <= l) {
return {LLONG_MIN,LLONG_MAX};
}
if (l <= x->l&&x->r <= r) {
return {x->maximum,x->minimum};
}
if (x->lft == NULL){
x->lft = new node(x->l,(x->l+x->r)/2);
}
if (x->rght == NULL){
x->rght = new node((x->l+x->r)/2,x->r);
}
pair<ll,ll> tempa=limitfind(x->lft,l,r);
pair<ll,ll> tempb=limitfind(x->rght,l,r);
return {max(tempa.f,tempb.f)+x->offset,min(tempa.s,tempb.s)+x->offset};
}
node *root;
vector<ll> strt[200069],nd[200069];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
root=new node(0,200069);
vector<int> rtn;
for (ll i = 0; i < v.size(); i++) {
strt[l[i]].push_back(i);
nd[r[i]+1].push_back(i);
}
add(root,0,200069,1000000069);
add(root,1,200069,-1000000069);
for (ll i = 0; i < c.size(); i++) {
for (ll j : strt[i]) {
add(root,j+2,200069,v[j]);
}
for (ll j : nd[i]) {
add(root,j+2,200069,-v[j]);
}
ll s=-1,e=200068;
while (s+1!=e) {
ll m=e-(e-s)/2;
pair<ll,ll> temp=limitfind(root, m, 200069);
if (temp.f-temp.s<=c[i]){
e=m;
}
else{
s=m;
}
}
ll temp=findval(root, 200068)-findval(root, e);
if (findval(root, e)-findval(root, e-1)>0) {
temp+=c[i];
}
rtn.push_back(temp);
}
return rtn;
}
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:94:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (ll i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
candies.cpp:100:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (ll i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1215 ms |
49696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
