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 int long long
using namespace std;
int mod=1e9+7;
int h[200000];
int w[200000];
int licz(int x,int y)
{
x+=y;
///x*(x+1)/2-y*(y+1)/2
int jeden=x*(x+1)/2;
int dwa=y*(y+1)/2;
jeden-=dwa;
jeden%=mod;
jeden+=mod*mod;
jeden%=mod;
return jeden;
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n;
cin>>n;
int wynik=0;
vector<pair<int,int> > Q;
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<=n;i++)
{
int x=h[i];
int y=w[i];
int suma=0;
while(Q.size() && Q.back().first>=x)
{
int cos1=(Q.back().first)*(Q.back().first+1);
cos1/=2;
cos1%=mod;
int cos2=licz(Q.back().second,suma);
cos1*=cos2;
cos1%=mod;
wynik+=cos1;
wynik%=mod;
suma+=Q.back().second;
suma%=mod;
Q.pop_back();
}
Q.push_back({x,(suma+y)%mod});
//cout<<"wrzucam "<<x<<" "<<y<<"\n";
}
int suma=0;
while(Q.size())
{
int cos1=(Q.back().first)*(Q.back().first+1);
cos1/=2;
cos1%=mod;
//cout<<cos1<<"\n";
int cos2=licz(Q.back().second,suma);
cos1*=cos2;
cos1%=mod;
wynik+=cos1;
//cout<<"dodaje "<<cos1<<"\n";
wynik%=mod;
suma+=Q.back().second;
suma%=mod;
Q.pop_back();
}
cout<<wynik;
return 0;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |