#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];
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];
dp[lp] = b[lp];
sum+=c2(b[lp]);
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;
ans+=val; ans%=mod;
}
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1880 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1884 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 |
1884 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2052 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |