| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 464793 | jamezzz | Dungeon 3 (JOI21_ho_t5) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define maxn 200005
int n,q,a[maxn],b[maxn],s,t,u,r[maxn];
ll x[maxn],ans[maxn];
vi disc;
stack<int> st;
int get(int i){
return upper_bound(all(disc),i)-disc.begin();
}
struct query{
int u,i,mult;
};
vector<query> qrys[maxn];
struct maxseg{
int s,e,m,v;maxseg *l,*r;
maxseg(int _s,int _e){
s=_s;e=_e;m=(s+e)>>1;v=0;
if(s!=e)l=new maxseg(s,m),r=new maxseg(m+1,e);
}
void up(int x,int nv){
if(s==x&&e==x){ v=nv;return; }
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=max(l->v,r->v);
}
int qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
}*die;
struct minseg{
int s,e,m;ii v;minseg *l,*r;
minseg(int _s,int _e){
s=_s;e=_e;m=(s+e)>>1;v={0,0};
if(s!=e)l=new minseg(s,m),r=new minseg(m+1,e);
}
void up(int x,ii nv){
if(s==x&&e==x){ v=nv;return; }
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=min(l->v,r->v);
}
ii qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return min(l->qry(x,m),r->qry(m+1,y));
}
}*getmin;
struct fw{
ll ft[maxn];
void init(){
for(int i=1;i<=n+1;++i){
ft[i]=0;
}
}
void up(int x,int y,ll v){
while(x<=n+1){
ft[x]+=v;x+=x&-x;
}
++y;
while(y<=n+1){
ft[y]-=v;y+=y&-y;
}
}
ll qry(int x){
ll res=0;
while(x){
res+=ft[x];x-=x&-x;
}
return res;
}
}*m=new fw(),*c=new fw();
int main(){
sf("%d%d",&n,&q);
die=new maxseg(1,n+1);
getmin=new minseg(1,n+1);
for(int i=1;i<=n;++i){
sf("%d",&a[i]);
die->up(i+1,a[i]);//max jump
x[i+1]=x[i]+a[i];
}
for(int i=1;i<=n;++i){
sf("%d",&b[i]);
getmin->up(i,{b[i],i});
}
for(int i=0;i<q;++i){
sf("%d%d%d",&s,&t,&u);
if(die->qry(s+1,t)>u){
//max distance is more than u, impossible
ans[i]=-1;
}
else{
qrys[s].pb({u,i,1});
//answer is cost from s to n+1 - cost from minpos to n+1 +
//cost to get from minpos to t, buying from minpos
int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
dbg("leftpos: %lld %d\n",x[t]-u,leftpos);
int minpos=getmin->qry(leftpos,t-1).se;
ans[i]=(x[t]-x[minpos])*b[minpos];
qrys[minpos].pb({u,i,-1});
dbg("%d: %d %d %d\n",s,u,i,1);
dbg("%d: %d %d %d\n",minpos,u,i,-1);
disc.pb(u);
}
}
disc.pb(INF);
sort(all(disc));
disc.erase(unique(all(disc)),disc.end());
m->init();c->init();
b[n+1]=-INF;st.push(n+1);
for(int i=n;i>=1;--i){
while(b[st.top()]>=b[i]){
int j=st.top();st.pop();
int dl=get(x[j]-x[i]);
int dr=get(x[r[j]]-x[i]);
m->up(dl+1,dr,-b[j]);
c->up(dl+1,dr,(x[j]-x[i])*b[j]);
c->up(dr+1,maxn-1,-(x[r[j]]-x[j])*b[j]);
}
r[i]=st.top();
int d=get(x[r[i]]-x[i]);
m->up(1,d,b[i]);//x<d:y=b[i]*x
c->up(d+1,maxn-1,(x[r[i]]-x[i])*b[i]);//x>=d:y=d*b[i]
st.push(i);
for(query q:qrys[i]){
ans[q.i]+=q.mult*(q.u*m->qry(get(q.u))+c->qry(get(q.u)));
dbg("%d %d %d %d: %lld\n",i,q.u,q.i,q.mult,q.mult*(q.u*m->qry(get(q.u))+c->qry(get(q.u))));
}
}
for(int i=0;i<q;++i){
pf("%lld\n",ans[i]);
}
}
/*
5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9
*/