Submission #36140278

---

Source Code Expand

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=100005;
int n,a[N],b[N],st[N],top,lc[N],rc[N];
struct node{
	map<int,LL>mp;
	LL s;
}tr[N];
void solve(int l,int r,int u,int mx){
	if(l>r){
		return;
	}
	mx=max(mx,a[u]);
	solve(l,u-1,lc[u],mx);
	solve(u+1,r,rc[u],mx);
	if(u-l>r-u){
		tr[u]=move(tr[lc[u]]);
		each(x,tr[rc[u]].mp){
			tr[u].mp[x.first]+=x.second;
		}
		tr[u].s+=tr[rc[u]].s;
		while(!tr[u].mp.empty()&&tr[u].mp.begin()->first<=a[u]){
			tr[u].s-=tr[u].mp.begin()->second;
			tr[u].mp.erase(tr[u].mp.begin());
		}
		while(!tr[u].mp.empty()&&tr[u].s>=b[u]){
			if(tr[u].s-tr[u].mp.begin()->second>b[u]){
				tr[u].s-=tr[u].mp.begin()->second;
				tr[u].mp.erase(tr[u].mp.begin());
			}else{
				tr[u].mp.begin()->second-=tr[u].s-b[u];
				tr[u].s=b[u];
				break;
			}
		}
		tr[u].mp[a[u]]+=b[u]-tr[u].s;
		tr[u].s=b[u];
	}else{
		tr[u]=move(tr[rc[u]]);
		each(x,tr[lc[u]].mp){
			tr[u].mp[x.first]+=x.second;
		}
		tr[u].s+=tr[lc[u]].s;
		while(!tr[u].mp.empty()&&tr[u].mp.begin()->first<=a[u]){
			tr[u].s-=tr[u].mp.begin()->second;
			tr[u].mp.erase(tr[u].mp.begin());
		}
		while(!tr[u].mp.empty()&&tr[u].s>=b[u]){
			if(tr[u].s-tr[u].mp.begin()->second>b[u]){
				tr[u].s-=tr[u].mp.begin()->second;
				tr[u].mp.erase(tr[u].mp.begin());
			}else{
				tr[u].mp.begin()->second-=tr[u].s-b[u];
				tr[u].s=b[u];
				break;
			}
		}
		tr[u].mp[a[u]]+=b[u]-tr[u].s;
		tr[u].s=b[u];
	}
}
int main(){
	rd(n);
	rep(i,1,n){
		rd(a[i]);
	}
	rep(i,1,n){
		rd(b[i]);
	}
	rep(i,1,n){
		while(top&&b[i]>b[st[top]]){
			lc[i]=st[top--];
		}
		rc[st[top]]=i;
		st[++top]=i;
	}
	solve(1,n,rc[0],0);
	int last=0;
	LL cur=tr[rc[0]].s;
	LL ans=0;
	each(x,tr[rc[0]].mp){
		ans+=1LL*(x.first-last)*cur;
		cur-=x.second;
		last=x.first;
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Judge Result