#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)%mod;
}
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])%mod); sum%=mod;
dp[v]+=dp[u]; dp[v]%=mod;
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++)
{
int L = l;
while((l < n) && (ab[l][0] >= C[i]))
{
int lp = ab[l][1];
dp[lp] = b[lp];
sum+=c2(b[lp]);
sum%=mod;
l++;
}
l = L;
while((l < n) && (ab[l][0] >= C[i]))
{
int lp = ab[l][1];
if(((lp+1) < n) && (a[lp+1] >= C[i]))
merge(lp, lp+1);
if(((lp-1) >= 0) && (a[lp-1] >= C[i]))
merge(lp, lp-1);
l++;
}
int val = (sum*((c2(C[i])-c2(C[i+1]))%mod))%mod;
ans+=val; ans%=mod;
}
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
1 ms |
1880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
13 ms |
3608 KB |
Output is correct |
4 |
Correct |
23 ms |
5212 KB |
Output is correct |
5 |
Correct |
23 ms |
4952 KB |
Output is correct |
6 |
Correct |
21 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Correct |
3 ms |
2140 KB |
Output is correct |
3 |
Correct |
15 ms |
3600 KB |
Output is correct |
4 |
Correct |
28 ms |
4956 KB |
Output is correct |
5 |
Correct |
25 ms |
4952 KB |
Output is correct |
6 |
Correct |
1 ms |
1880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
3 ms |
2140 KB |
Output is correct |
4 |
Correct |
12 ms |
3416 KB |
Output is correct |
5 |
Correct |
23 ms |
4956 KB |
Output is correct |
6 |
Correct |
29 ms |
4956 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
3 ms |
2396 KB |
Output is correct |
9 |
Correct |
12 ms |
3864 KB |
Output is correct |
10 |
Correct |
22 ms |
6096 KB |
Output is correct |
11 |
Correct |
22 ms |
6104 KB |
Output is correct |
12 |
Correct |
1 ms |
1884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |