Submission #48241737

---

Source Code Expand

// LUOGU_RID: 138508616
#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef atcoder::modint998244353 mint;

#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)

#ifdef EXODUS
	#define Debug(...) fprintf(stderr,__VA_ARGS__)
#else
	#define Debug(...) 0
#endif

//=========================================================================================================
// Something about IO

template<typename T>
void read(T &x){
	x=0;T flg=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=flg;
}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

//=========================================================================================================
// Define the global variables here.

bool membg=0;


constexpr int N=2e5+7;
int n,a[2][N];
ll disl[2][2][N],disr[2][2][N];
mint ans=0;

bool memed=0;

//=========================================================================================================
// Code here.

void solve(int l,int r){
	if(l>r)return;
	int mid=(l+r)>>1;
	solve(l,mid-1),solve(mid+1,r);
	disl[0][0][mid]=a[0][mid];
	disl[0][1][mid]=a[0][mid]+a[1][mid];
	disl[1][0][mid]=a[0][mid]+a[1][mid];
	disl[1][1][mid]=a[1][mid];
	for(int i=mid-1;i>=l;i--)
		for(int j=0;j<2;j++)
			disl[j][0][i]=min(disl[j][0][i+1]+a[0][i],disl[j][1][i+1]+a[0][i]+a[1][i]),
			disl[j][1][i]=min(disl[j][1][i+1]+a[1][i],disl[j][0][i+1]+a[0][i]+a[1][i]);
	disr[0][0][mid]=0;
	disr[0][1][mid]=a[1][mid];
	disr[1][0][mid]=a[0][mid];
	disr[1][1][mid]=0;
	for(int i=mid+1;i<=r;i++)
		for(int j=0;j<2;j++)
			disr[j][0][i]=min(disr[j][0][i-1]+a[0][i],disr[j][1][i-1]+a[0][i]+a[1][i]),
			disr[j][1][i]=min(disr[j][1][i-1]+a[1][i],disr[j][0][i-1]+a[0][i]+a[1][i]);
	vector<pair<ll,ll>>L,R;
	for(int i=l;i<=mid;i++)
		for(int j=0;j<2;j++)
			L.eb(disl[0][j][i],disl[1][j][i]);
	for(int i=mid;i<=r;i++)
		for(int j=0;j<2;j++)
			R.eb(disr[0][j][i],disr[1][j][i]);
	sort(L.begin(),L.end(),[&](pair<ll,ll>&lhs,pair<ll,ll>&rhs){return lhs.first-lhs.second>rhs.first-rhs.second;});
	sort(R.begin(),R.end(),[&](pair<ll,ll>&lhs,pair<ll,ll>&rhs){return lhs.first-lhs.second<rhs.first-rhs.second;});
    mint pre=0,suf=0,prec=0,sufc=0,res=0;
	for(auto [x,y]:R)suf+=y,sufc++;
	for(int i=0,j=-1;i<(int)L.size();i++){
		for(;j+1<(int)R.size()&&L[i].first-L[i].second+R[j+1].first-R[j+1].second<0;j++)
			suf-=R[j+1].second,sufc--,pre+=R[j+1].first,prec++;
		res+=L[i].first*prec+L[i].second*sufc+pre+suf;
	}
	ans+=2*res;
}

void solve(){
	read(n);
	rep(i,0,1)rep(j,1,n)read(a[i][j]);
	solve(1,n);
	for(int i=1;i<=n;i++)ans-=3ll*(a[0][i]+a[1][i]);
	printf("%d\n",ans.val());
	return;
}


//=========================================================================================================

int main(){
	Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
	int timbg=clock();
	int T=1;
	while(T--)solve();
	int timed=clock();
	Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
	fflush(stdout);
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:20:28: warning: statement has no effect [-Wunused-value]
   20 |         #define Debug(...) 0
      |                            ^
Main.cpp:105:9: note: in expansion of macro ‘Debug’
  105 |         Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
      |         ^~~~~
Main.cpp:20:28: warning: statement has no effect [-Wunused-value]
   20 |         #define Debug(...) 0
      |                            ^
Main.cpp:110:9: note: in expansion of macro ‘Debug’
  110 |         Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
      |         ^~~~~
Main.cpp:106:13: warning: unused variable ‘timbg’ [-Wunused-variable]
  106 |         int timbg=clock();
      |             ^~~~~
Main.cpp:109:13: warning: unused variable ‘timed’ [-Wunused-variable]
  109 |         int timed=clock();
      |             ^~~~~

Judge Result