#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector< int > add[N] , rem[N];
int n , m;
long long lazy[4 * N] ;
struct S{
long long mn , mx;
int mnIdx , mxIdx;
S(long long mn,long long mx){this->mn = mn, this->mx = mx;}
S(){mn = mx = 0;}
void make(const S & l , const S & r){
if(l.mn < r.mn)
mn = l.mn , mnIdx = l.mnIdx;
else
mn = r.mn , mnIdx = r.mnIdx;
if(r.mx >= l.mx)
mx = r.mx , mxIdx = r.mxIdx;
else
mx = l.mx , mxIdx = l.mxIdx;
}
} seg[4 * N];
void fix(int s,int e,int idx){
seg[idx].mn += lazy[idx];
seg[idx].mx += lazy[idx];
if(s != e){
lazy[(idx << 1)] += lazy[idx];
lazy[(idx << 1) + 1] += lazy[idx];
}
lazy[idx] = 0;
}
int l , r , val;
void build(int s,int e, int idx){
if(s == e){
seg[idx].mnIdx = seg[idx].mxIdx = s;
return;
}
build(s , ((s+e) >> 1),(idx << 1));
build(((s+e) >> 1) + 1,e,(idx << 1) + 1);
seg[idx].make(seg[(idx << 1)] , seg[(idx << 1) + 1]);
}
void update(int s,int e,int idx){
if(lazy[idx]) fix(s , e, idx);
if(s > r || e < l)
return;
if(s >= l && e <= r){
lazy[idx] += val;
fix(s , e, idx);
return;
}
update(s , (s + e) >> 1 , (idx << 1));
update(((s+e) >> 1) + 1, e , (idx << 1) + 1);
seg[idx].make(seg[(idx << 1)] , seg[(idx << 1) + 1]);
}
void getMx(int s,int e, int idx,long long &mxVal,int &mxIdx){
fix(s , e, idx);
if(s > r || e < l)
return;
if(s >= l && e <= r){
if(seg[idx].mx >= mxVal){
mxVal = seg[idx].mx;
mxIdx = seg[idx].mxIdx;
}
return;
}
getMx(s , ((s+e) >> 1),(idx << 1) , mxVal , mxIdx);
getMx(((s+e) >> 1) + 1, e , (idx << 1) + 1 , mxVal , mxIdx);
}
void getMn(int s,int e,int idx,long long& mnVal, int& mnIdx){
fix(s , e , idx);
if(s > r || e < l)
return;
if(s >= l && e <= r){
if(seg[idx].mn <= mnVal){
mnVal = seg[idx].mn;
mnIdx = seg[idx].mnIdx;
}
return;
}
getMn(s , ((s+e) >> 1),(idx << 1) , mnVal , mnIdx);
getMn(((s+e) >> 1) + 1, e , (idx << 1) + 1 , mnVal , mnIdx);
}
bool getFirstMn(int s,int e,int idx,long long &mnVal,int &mnIdx ,long long val){
//cout << s << " " << e << " " << idx << " " << l << " " << r << endl;
fix(s , e , idx);
if(s > r || e < l)
return false;
if(s >= l && e <= r){
if(seg[idx].mn >= val) return false;
if(s == e){
mnVal = seg[idx].mn;
mnIdx = seg[idx].mnIdx;
return true;
}
if(seg[(idx << 1) + 1].mn < val)
return getFirstMn(((s+e) >> 1) + 1 , e , (idx << 1) + 1 , mnVal , mnIdx , val);
return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);
}
if(getFirstMn(((s+e) >> 1) + 1 , e , (idx << 1) + 1 , mnVal , mnIdx , val))
return true;
return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);
}
int solve(int c){
// cout << "solve " << c << endl;
long long mnVal , curMn , mxVal;
int mnIdx , curIdx , mxIdx;
l = 0 , r = m - 1;
mnVal = (long long)1e18;
getMn(0 , m - 1 , 1, mnVal , mnIdx);
//cout << mnIdx << " " << mnVal << endl;
int low = mnIdx + 1 , high = m - 1 , res = mnIdx , mid;
while(low <= high){
mid = (low + high) / 2;
//cout << "check " << mid << endl;
l = mid , r = m - 1;
curMn = (long long)1e18;
getMn(0 , m - 1 , 1 , curMn , curIdx);
//cout << "curMn =" << " " << curMn << " " << curIdx << endl;
l = mnIdx , r = curIdx;
getFirstMn(0 , m - 1 , 1, curMn , curIdx , curMn);
//cout << "one step to left " << curMn << " " << curIdx << endl;
l = curIdx , r = m - 1;
mxVal = -(long long)1e18;
getMx(0 , m - 1 , 1 , mxVal , mxIdx);
l = mxIdx , r = m - 1;
curMn = (long long)1e18;
getMn(0 , m - 1 , 1 , curMn , curIdx);
//cout << "check " << mid << endl;
//cout << mxIdx << " " << curIdx << " " << curMn << " " << mxVal << endl;
if(curIdx == mxIdx || (curMn + c - mxVal) >= 0)
high = mid - 1;
else
res = mid , low = mid + 1;
}
//cout << "done with res " << res << endl;
curMn = (long long)1e18;
l = r = m - 1;
getMn(0 , m - 1 , 1 , curMn , curIdx);
mnVal = (long long)1e18;
l = r = res;
getMn(0 , m - 1 , 1 ,mnVal , mnIdx);
mxVal = (long long)-1e18;
l = res , r = m - 1;
getMx(0 , m - 1 , 1 , mxVal , mxIdx);
//cout << mnIdx << " " << mxIdx << " " << curIdx << " " << mnVal << " " << mxVal << " " << curMn << endl;
if(mxIdx != mnIdx && mxVal - mnVal >= c){
return curMn - mxVal + c;
}
return curMn - mnVal;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
n = (int)c.size();
m = (int)l.size() + 1;
vector< int > s(n , 0);
for(int i = 0 ;i < (int)l.size();i++){
add[l[i]].push_back(i);
rem[r[i] + 1].push_back(i);
}
build(0 , m - 1 , 1);
for(int i = 0 ;i < n;i++){
for(int j = 0 ;j < (int)add[i].size();j++){
::l = add[i][j] + 1;
::r = m - 1;
val = v[add[i][j]];
update(0 , m - 1 , 1);
}
for(int j = 0 ;j < (int)rem[i].size();j++){
::l = rem[i][j] + 1;
::r = m - 1;
val = -v[rem[i][j]];
update(0 , m - 1 , 1);
}
s[i] = solve(c[i]);
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28364 KB |
Output is correct |
| 2 |
Correct |
16 ms |
28472 KB |
Output is correct |
| 3 |
Correct |
17 ms |
28508 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4691 ms |
46868 KB |
Output is correct |
| 2 |
Correct |
4690 ms |
46836 KB |
Output is correct |
| 3 |
Correct |
4602 ms |
46828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28496 KB |
Output is correct |
| 2 |
Incorrect |
526 ms |
40156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28476 KB |
Output is correct |
| 2 |
Correct |
16 ms |
28448 KB |
Output is correct |
| 3 |
Correct |
183 ms |
39024 KB |
Output is correct |
| 4 |
Correct |
1561 ms |
31044 KB |
Output is correct |
| 5 |
Correct |
4803 ms |
41436 KB |
Output is correct |
| 6 |
Correct |
4541 ms |
41428 KB |
Output is correct |
| 7 |
Correct |
4734 ms |
41440 KB |
Output is correct |
| 8 |
Correct |
4977 ms |
41436 KB |
Output is correct |
| 9 |
Correct |
4265 ms |
41436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28364 KB |
Output is correct |
| 2 |
Correct |
16 ms |
28472 KB |
Output is correct |
| 3 |
Correct |
17 ms |
28508 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
