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>
using namespace std;
#define int long long
#define in array<int, 2>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int mod = 1e9+7;
const int MX = 1e5+5;
int c2(int x)
{
return (x*(x+1))/2;
}
int sum;
vector<int> pa(MX, -1);
vector<int> dp(MX, 0);
int leader(int u)
{
if(pa[u] < 0)
return u;
else
return pa[u] = leader(pa[u]);
}
void merge(int u, int v)
{
u = leader(u); v = leader(v);
if(u==v)
return;
if(pa[u] < pa[v])
swap(u, v);
pa[v]+=pa[u];
sum+=(dp[u]*dp[v]);
dp[v]+=dp[u];
pa[u] = v;
return;
}
signed main()
{
fast();
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
vector<in> ab(n);
for(int i = 0; i < n; i++)
{
cin >> a[i];
ab[i][0] = a[i];
}
for(int i = 0; i < n; i++)
{
cin >> b[i];
ab[i][1] = i;
}
sort(ab.rbegin(), ab.rend());
vector<int> C{ab[0][0]};
for(auto p: ab)
{
if(C.back() != p[0])
C.pb(p[0]);
}
int ans = 0;
int l = 0; int D = C.size(); C.pb(0);
for(int i = 0; i < D; i++)
{
while((l < n) && (ab[l][0] >= C[i]))
{
int lp = ab[l][1];
if(dp[lp] == 0)
dp[lp] = b[lp];
sum+=c2(b[lp]);
if(((lp+1) < n) && (a[lp+1] >= C[i]))
{
if(dp[lp+1] == 0)
dp[lp+1] = b[lp+1];
merge(lp, lp+1);
}
if(((lp-1) >= 0) && (a[lp-1] >= C[i]))
{
if(dp[lp-1] == 0)
dp[lp-1] = b[lp-1];
merge(lp, lp-1);
}
l++;
}
int val = (sum*(c2(C[i])-c2(C[i+1])))%mod;
ans+=val; ans%=mod;
}
cout << ans << "\n";
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... |