이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int mod=(int)1e9+7;
int dpl[10002][20002];
int dpr[10002][20002];
int getsuml(int i,int l,int r)
{
return (dpl[i][r]-dpl[i][l-1]+mod)%mod;
}
int getsumr(int i,int l,int r)
{
return (dpr[i][r]-dpr[i][l-1]+mod)%mod;
}
signed main()
{
int n;
cin>>n;
vector<int>arr(n+1);
vector<int>brr(n+1);
for(int i=1;i<=n;i++)cin>>arr[i];
for(int i=1;i<=n;i++)cin>>brr[i];
set<int>st;
for(auto i:arr)st.insert(i);
for(auto i:brr)st.insert(i);
int cnt=1;
vector<int>hi;
hi.push_back(0);
for(auto i:st)
{
cnt++;
hi.push_back(i);
}
int a7a=*max_element(arr.begin(),arr.end());
a7a=max(a7a,*max_element(brr.begin(),brr.end()));
a7a=lower_bound(hi.begin(),hi.end(),a7a)-hi.begin();
long long ans=0;
for(int i=1;i<=n;i++)
{
// ans=ans-(((arr[i]*((1ll<<(n-1))%mod))%mod)+mod)%mod;
// ans=ans-(((brr[i]*((1ll<<(n-1))%mod))%mod)+mod)%mod;
}
// cout<<dpl.size();
// return 0;
dpl[0][0]=1;
for(int i=1;i<=n;i++)arr[i]=lower_bound(hi.begin(),hi.end(),arr[i])-hi.begin(),brr[i]=lower_bound(hi.begin(),hi.end(),brr[i])-hi.begin();
for(int i=1;i<=n;i++)
{
for(int j=arr[i];j>=0;j--)
{
dpl[i][arr[i]]+=dpl[i-1][j];
if(dpl[i][arr[i]]>=mod)
dpl[i][arr[i]]-=mod;
}
for(int j=arr[i]+1;j<=a7a;j++)
{
dpl[i][j]+=dpl[i-1][j];
if(dpl[i][j]>=mod)
dpl[i][j]-=mod;
}
for(int j=brr[i];j>=0;j--)
{
dpl[i][brr[i]]+=dpl[i-1][j];
if(dpl[i][brr[i]]>=mod)
dpl[i][brr[i]]-=mod;
}
for(int j=brr[i]+1;j<=a7a;j++)
{
dpl[i][j]+=dpl[i-1][j];
if(dpl[i][j]>=mod)
dpl[i][j]-=mod;
}
}
dpr[n+1][0]=1;
for(int i=n;i>=1;i--)
{
for(int j=arr[i];j>=0;j--)
{
dpr[i][arr[i]]+=dpr[i+1][j];
if(dpr[i][arr[i]]>=mod)
dpr[i][arr[i]]-=mod;
}
for(int j=arr[i]+1;j<=a7a;j++)
{
dpr[i][j]+=dpr[i+1][j];
if(dpr[i][j]>=mod)
dpr[i][j]-=mod;
}
for(int j=brr[i];j>=0;j--)
{
dpr[i][brr[i]]+=dpr[i+1][j];
if(dpr[i][brr[i]]>=mod)
dpr[i][brr[i]]-=mod;
}
for(int j=brr[i]+1;j<=a7a;j++)
{
dpr[i][j]+=dpr[i+1][j];
if(dpr[i][j]>=mod)
dpr[i][j]-=mod;
}
}
// cout<<ans<<endl;
for(int i=0;i<=n+1;i++)
for(int j=1;j<=a7a;j++){
dpl[i][j]+=dpl[i][j-1];
if(dpl[i][j]>=mod)
dpl[i][j]-=mod;
dpr[i][j]+=dpr[i][j-1];
if(dpr[i][j]>=mod)
dpr[i][j]-=mod;
}
for(int i=1;i<=n;i++)
{
for(int j=min(arr[i],brr[i]);j<=a7a;j++)
{
if(j>=arr[i]){
long long x=getsuml(i-1,j,j);
x*=getsumr(i+1,j,a7a);
x%=mod;
ans+=((hi[j]-hi[arr[i]])*x)%mod;
x=getsumr(i+1,j,j);
x*=getsuml(i-1,j+1,a7a);
x%=mod;
ans+=((hi[j]-hi[arr[i]])*x)%mod;
if(ans>=mod)ans-=mod;
}
if(j>=brr[i])
{
long x=getsuml(i-1,j,j);
x*=getsumr(i+1,j,a7a);
x%=mod;
ans+=((hi[j]-hi[brr[i]])*x)%mod;
x=getsumr(i+1,j,j);
x*=getsuml(i-1,j+1,a7a);
x%=mod;
ans+=((hi[j]-hi[brr[i]])*x)%mod;
if(ans>=mod)ans-=mod;
}
}
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |