Submission #464799

#	Time	Username	Problem	Language	Result	Execution time	Memory
464799		jamezzz	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	990 ms	70388 KiB

Main

#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(ll 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=lower_bound(x+1,x+n+1,x[t]-u)-x;
			int minpos=getmin->qry(max(s,leftpos),t-1).se;
			ans[i]=(x[t]-x[minpos])*b[minpos];
			qrys[minpos].pb({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)));
		}
	}
	
	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
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:114:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  sf("%d%d",&n,&q);
      |    ^
Main.cpp:120:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   sf("%d",&a[i]);
      |     ^
Main.cpp:125:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |   sf("%d",&b[i]);
      |     ^
Main.cpp:130:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   sf("%d%d%d",&s,&t,&u);
      |     ^

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44