#include <bits/stdc++.h>
using namespace std;
# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"
const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;
const int mod = 1e9+7;
int F[cnst];
int inv[cnst];
int A(int a, int b) {return ((a%mod)+(b%mod))%mod;}
int S(int a, int b) {return ((a%mod)-(b%mod)+mod)%mod;}
int M(int a, int b) {return ((a%mod)*(b%mod))%mod;}
int E(int b, int p) {
if(!p) return 1;
return (p%2 ? M(E(M(b, b), p/2), b) : E(M(b, b), p/2));
}
int C(int n, int r) {return M(M(F[n], inv[n-r]), inv[r]);}
void prefac(int maxn) {
F[0] = 1;
for(int i = 1; i<=maxn; i++) F[i] = M(F[i-1], i);
inv[maxn] = E(F[maxn], mod-2);
for(int i = maxn-1; i>=0; i--) inv[i] = M(inv[i+1], i+1);
}
int gcd(int a, int b) {return b ? gcd(b, a%b): a;}
int lcm(int a, int b) {return M(a/gcd(a, b), b);}
int root[cnst];
int find(int x) {return root[x] == x ? x : root[x] = find(root[x]);}
int merge(int x, int y) {
return root[find(x)] = find(y);
}
void solve() {
int n; cin >> n;
int H[n+5];
int W[n+5];
for(int i = 1; i<=n; i++) cin >> H[i];
for(int j = 1; j<=n; j++) cin >> W[j];
int ans = 0;
vector<tuple<int, int, int>> vec;
for(int i = 1; i<=n; i++) vec.pb({H[i], W[i], i}), ans = A(ans, M(H[i]*(H[i]+1)/2, W[i]*(W[i]+1)/2));
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
bool vis[n+5];
int count[n+5];
int L[n+5];
int R[n+5];
int mx[n+5];
int tt[n+5];
memset(count, 0, sizeof(count));
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++) L[i] = R[i] = i;
for(auto [h, w, id]: vec) {
count[id] = w; vis[id] = 1;
// mx[id] = h; tt[id] = M(h, w);
if(vis[id-1] && vis[id+1] && id != 1 && id != n) {
ans = A(ans, M(h*(h+1)/2, S(M(A(count[id-1], w), A(count[id+1], w)), M(w, w))));
count[L[id-1]] += count[L[id+1]]+w;
count[R[id+1]] += count[R[id-1]]+w;
}
else if(vis[id-1] && id != 1) {
R[L[id-1]] = id;
L[id] = L[id-1];
ans = A(ans, M(M(w, count[id-1]), h*(h+1)/2));
count[L[id]] += count[id];
count[id] += count[id-1];
}
else if(vis[id+1] && id != n) {
L[R[id+1]] = id;
R[id] = R[id+1];
ans = A(ans, M(M(w, count[id+1]), h*(h+1)/2));
count[R[id]] += count[id];
count[id] += count[id-1];
}
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
if(mutipletestcase) cin >> t;
while(t--) solve();
}
Compilation message
fancyfence.cpp: In function 'void solve()':
fancyfence.cpp:69:9: warning: unused variable 'mx' [-Wunused-variable]
69 | int mx[n+5];
| ^~
fancyfence.cpp:70:9: warning: unused variable 'tt' [-Wunused-variable]
70 | int tt[n+5];
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |