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 double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int MAX = 100010;
int n;
int h[MAX], w[MAX];
bool vis[MAX];
int p[MAX], dep[MAX];
int wsum[MAX], l[MAX], r[MAX];
int res;
int findp(int v){
if(v == p[v]) return v;
return p[v] = findp(p[v]);
}
void uni(int u, int v){
int pu = findp(u);
int pv = findp(v);
if(pu == pv) return;
if(dep[pu] < dep[pv]) swap(pu, pv);
p[pv] = pu;
if(dep[pu] > dep[pv]) dep[pu]++;
wsum[pu] += wsum[pv];
l[pu] = min(l[pu], l[pv]);
r[pu] = max(r[pu], r[pv]);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("fancyfence_sample.txt", "r", stdin);
cin>>n;
FOR(i, 1, n, 1){
cin>>h[i];
}
FOR(i, 1, n, 1){
cin>>w[i];
}
FOR(i, 1, n, 1){
vis[i] = 0;
p[i] = i;
dep[i] = 0;
wsum[i] = w[i];
l[i] = r[i] = i;
}
vector<pii> owo;
FOR(i, 1, n, 1){
owo.eb(h[i], i);
}
sort(owo.begin(), owo.end());
reverse(owo.begin(), owo.end());
for(pii i : owo){
int id = i.S;
vis[id] = 1;
if(vis[id - 1]) uni(id - 1, id);
if(vis[id + 1]) uni(id, id + 1);
int U = h[id];
int D = max(h[l[findp(id)] - 1], h[r[findp(id)] + 1]) + 1;
int W = wsum[findp(id)] % MOD;
res += (((U + D) * (U - D + 1) / 2) % MOD) * ((W * (W + 1) / 2) % MOD);
res %= MOD;
//cerr<<"U = "<<U<<", D = "<<D<<", res += "<<(((U + D) * (U - D + 1) / 2) % MOD) * ((W * (W + 1) / 2) % MOD)<<endl;
}
cout<<res<<'\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... |