#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define DBG 0
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
const Int INF = 1e9+5;
const int N = 2e5+5;
int n, q;
V<int> c;
V<int> ql, qr, qv;
#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
// st.qry(t) = height at time t
struct St{
Int mx[2*N], mn[2*N], lz[2*N];
void upd(int l,int r,Int x,int v=0,int tl=0,int tr=q){
if(r<tl || tr<l) return;
if(l<=tl && tr<=r){
mx[v] += x; mn[v] += x; lz[v] += x;
return;
}
upd(l,r,x, lc,tl,mid);
upd(l,r,x, rc,mid+1,tr);
mx[v] = lz[v] + max(mx[lc], mx[rc]);
mn[v] = lz[v] + min(mn[lc], mn[rc]);
}
Int qryMax(int l,int r=q,int v=0,int tl=0,int tr=q){
if(r<tl || tr<l) return -INF*INF;
if(l<=tl && tr<=r) return mx[v];
return lz[v] + max({
qryMax(l,r, lc,tl,mid), qryMax(l,r, rc,mid+1,tr)
});
}
Int qryMin(int l,int r=q,int v=0,int tl=0,int tr=q){
if(r<tl || tr<l) return INF*INF;
if(l<=tl && tr<=r) return mn[v];
return lz[v] + min({
qryMin(l,r, lc,tl,mid), qryMin(l,r, rc,mid+1,tr)
});
}
} st;
// events
V<int> ev[N];
V<int> distribute_candies(V<int> _c,V<int> _ql,V<int> _qr,V<int> _qv){
c.swap(_c); ql.swap(_ql); qr.swap(_qr); qv.swap(_qv);
n = c.size();
// dummy updates to guarantee both walls will be touched
reverse(all(ql)); reverse(all(qr)); reverse(all(qv));
ql.push_back(0); qr.push_back(n-1); qv.push_back(-INF);
ql.push_back(0); qr.push_back(n-1); qv.push_back(+INF);
reverse(all(ql)); reverse(all(qr)); reverse(all(qv));
q = ql.size();
// sort update events by l and r
dbg(q);
rep(i,0,q){
cerr << ql[i] _ qr[i] _ qv[i] << nl;
ev[ql[i]].push_back(i);
ev[qr[i]+1].push_back(i);
}
cerr << nl;
V<int> vans(n);
rep(i,0,n){
for(int e : ev[i]){
// enable update
if(ql[e]==i){
st.upd(e,q, qv[e]);
}
// disable update
else{
st.upd(e,q, -qv[e]);
}
// rep(i,0,q) cerr << st.qryMax(i,i) << " ";
// cerr << nl << nl;
}
// rep(i,0,q) cerr << st.qryMax(i,i) << " ";
// cerr << nl << nl;
// find last wall touch
// if MAX-MIN>=c[i], that means in the future, we will touch another wall
int t = 0;
for(int J=1<<20; J; J/=2)
if(t+J<q && st.qryMax(t+J)-st.qryMin(t+J)>=c[i]) t+=J;
t++;
dbg(t);
dbg(st.qryMax(t)-st.qryMin(t));
// find base wall and calculate ans
Int ans;
Int h = st.qryMax(q), base;
// if last movement was UP, that means MAX is ceiling wall
if(qv[t] > 0){
base = st.qryMax(t) - c[i];
assert(st.qryMax(t)==st.qryMax(t,t));
}
// if last movement was DOWN, that means MIN is floor/base wall
else{
base = st.qryMin(t);
assert(st.qryMin(t)==st.qryMin(t,t));
}
// ans is relative height from base
ans = h - base;
vans[i] = ans;
dbg(h);
dbg(base);
cerr << nl << nl;
// if(i==1) return vans;
}
return vans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
9964 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
147 ms |
37500 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
10024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
9940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
9964 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
