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>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int mod=1e9+7;
const int M=5e5+10;
int n,a[M],b[M];
namespace sub1
{
const int M=30;
int x[M],y[M],kq=0;
void ktra()
{
fori(i,1,n) y[i]=1e9;
int l=0,r=0;
fori(i,1,n) {
l=max(l,x[i]);
y[i]=min(y[i],l);
}
for(int i=n;i!=0;i--) {
r=max(r,x[i]);
y[i]=min(y[i],r);
}
fori(i,1,n) kq=(kq+max(0ll,y[i]-x[i]))%mod;
}
void duyet(int i)
{
if(i==n+1) ktra();
else {
fori(j,0,1) {
if(j) x[i]=a[i];
else x[i]=b[i];
duyet(i+1);
}
}
}
void solve()
{
duyet(1);
cout << kq ;
}
}
namespace sub3
{
const int M=1e4+10;
const int N=1e3+10;
int f[M][N],g[M][N],kq=0;
void solve()
{
int lim=0;
fori(i,1,n) lim=max({lim,a[i],b[i]});
f[0][0]=1;
fori(i,1,n) {
fori(j,0,lim) {
int val=max(a[i],j);
int val2=max(b[i],j);
f[i][val]=(f[i-1][j]+f[i][val])%mod;
f[i][val2]=(f[i-1][j]+f[i][val2])%mod;
// cout << f[i][val] << " " << f[i][val2] << "\n";
}
}
g[n+1][0]=1;
for(int i=n;i!=0;i--) {
fori(j,0,lim) {
int val=max(a[i],j);
int val2=max(b[i],j);
g[i][val]=(g[i+1][j]+g[i][val])%mod;
g[i][val2]=(g[i+1][j]+g[i][val2])%mod;
}
}
fori(i,1,n) {
int sum=0;
for(int j=lim;j>=min(a[i],b[i]);j--) {
sum=(sum+g[i+1][j])%mod;
if(a[i]<=j) kq=(kq+(f[i-1][j]*sum)%mod*(j-a[i])%mod)%mod;
if(b[i]<=j) kq=(kq+(f[i-1][j]*sum)%mod*(j-b[i])%mod)%mod;
}
sum=0;
for(int j=lim;j>=min(a[i],b[i]);j--) {
if(a[i]<=j) kq=(kq+(sum*g[i+1][j])%mod*(j-a[i])%mod)%mod;
if(b[i]<=j) kq=(kq+(sum*g[i+1][j])%mod*(j-b[i])%mod)%mod;
sum=(sum+f[i-1][j])%mod;
}
}
cout << kq;
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r"))
{
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n;
fori(i,1,n) cin >> a[i];
fori(i,1,n) cin >> b[i];
if(n<=20) sub1::solve();
else sub3::solve();
//sub3::solve();
}
Compilation message (stderr)
Main.cpp: In function 'int32_t main()':
Main.cpp:101:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:108:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |