#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
const ll INF=1e18+7;
ll F1[4*LIM], F2[4*LIM], mi[4*LIM], ma[4*LIM], sufix[LIM], N=1;
void upd(int v, ll x) {
v+=N;
mi[v]=ma[v]=x;
v/=2;
while(v) {
mi[v]=min(mi[2*v], mi[2*v+1]);
ma[v]=max(ma[2*v], ma[2*v+1]);
v/=2;
}
}
ll cntmi(int l, int r) {
l+=N; r+=N;
ll ans=min(mi[l], mi[r]);
while(l/2!=r/2) {
if(l%2==0) ans=min(ans, mi[l+1]);
if(r%2==1) ans=min(ans, mi[r-1]);
l/=2; r/=2;
}
return ans;
}
ll cntma(int l, int r) {
l+=N; r+=N;
ll ans=max(ma[l], ma[r]);
while(l/2!=r/2) {
if(l%2==0) ans=max(ans, ma[l+1]);
if(r%2==1) ans=max(ans, ma[r-1]);
l/=2; r/=2;
}
return ans;
}
int znajdz_gore(int v, int l, int r, ll x) {
if(l==r) return l;
if(F1[v]<x) return -1;
int mid=(l+r)/2;
if(F1[2*v+1]>=x) return znajdz_gore(2*v+1, mid+1, r, x);
else return znajdz_gore(2*v, l, mid, x);
}
int znajdz_dol(int v, int l, int r, ll x) {
if(l==r) return l;
if(F2[v]<x) return -1;
int mid=(l+r)/2;
if(F2[2*v+1]>=x) return znajdz_dol(2*v+1, mid+1, r, x);
else return znajdz_dol(2*v, l, mid, x);
}
vector<int>solve(vector<ll>c, vector<ll>v) {
ll n=c.size(), q=v.size();
for(int i=q-1; i>=0; --i) sufix[i]=sufix[i+1]+v[i];
while(N<=q) N*=2;
stack<pair<ll,ll>>kolma, kolmi;
kolma.push({INF, -1});
kolmi.push({-INF, -1});
ll sum=0;
rep(i, q) {
sum+=v[i];
upd(i+1, sum);
while(kolma.top().st<sum) kolma.pop();
F1[N+i]=sum-cntmi(kolma.top().nd+1, i+1);
while(kolmi.top().st>sum) kolmi.pop();
F2[N+i]=cntma(kolmi.top().nd+1, i+1)-sum;
kolma.push({sum, i});
kolmi.push({sum, i});
}
for(int i=N-1; i>=0; --i) {
F1[i]=max(F1[2*i], F1[2*i+1]);
F2[i]=max(F2[2*i], F2[2*i+1]);
}
vector<int>ans;
rep(i, n) {
int gora=znajdz_gore(1, 0, N-1, c[i]);
int dol=znajdz_dol(1, 0, N-1, c[i]);
if(gora>=dol) {
if(gora==-1) {
ans.pb(sufix[0]);
} else {
ans.pb(c[i]+sufix[gora+1]);
}
} else {
ans.pb(sufix[dol+1]);
}
}
return ans;
}
vector<int>distribute_candies(vector<int>c, vector<int>l, vector<int>r, vector<int>v) {
vector<ll>c1, v1;
for(auto i : c) c1.pb(i);
for(auto i : v) v1.pb(i);
return solve(c1, v1);
}
/*int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int>c;
rep(i, n) {
int a;
cin >> a;
c.pb(a);
}
int q;
cin >> q;
vector<int>l, r, v;
rep(i, q) {
int a, b, c;
cin >> a >> b >> c;
l.pb(a);
r.pb(b);
v.pb(c);
}
vector<int>ans=distribute_candies(c, l, r, v);
for(auto i : ans) cout << i << " ";
cout << '\n';
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
37912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
108 ms |
26040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
