이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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));
// for(int i = 1; i<=n; i++) cerr << H[i] << " " << W[i] << endl;
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];
memset(count, 0, sizeof(count));
memset(vis, 0, sizeof(vis));
for(int i = 1; i<=n; i++) L[i] = R[i] = i;
cerr << ans << endl;
for(auto [h, w, id]: vec) {
count[id] = w; vis[id] = 1;
// mx[id] = h; tt[id] = M(h, w);
// cerr << h << " " << w << " " << id << endl;
cerr << count[id-1] << " " << count[id] << " " << count[id+1] << endl;
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;
R[L[id-1]] = R[id+1];
L[R[id+1]] = L[id-1];
}
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[L[id]];
}
else if(vis[id+1] && id != n) {
L[R[id+1]] = id;
R[id] = R[id+1];
// cerr << L[id] << " " << R[id] << endl;
ans = A(ans, M(M(w, count[id+1]), h*(h+1)/2));
count[R[id]] += count[id];
count[id] = count[R[id]];
}
// for(int i = 1; i<=n; i++) cerr << count[i] << " "; cerr << endl;
// cerr << ans << endl;
}
cout << ans%mod << endl;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
if(mutipletestcase) cin >> t;
while(t--) solve();
}
# | 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... |