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;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll LOG = 31;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'
ll n, m;
ll a [MAXN], b [MAXN], pf [MAXN];
vll v;
// V(x, y) = dep[x] + dep[y] - 2*dep[lca]
// cari V(x, y) terkecil ke (1 - 10^5)
ll sum(ll x, ll y){return ((x%MOD)+(y%MOD))%MOD;}
ll sub(ll x, ll y){return ((x%MOD)-(y%MOD) + 2*MOD) % MOD;}
ll mul(ll x, ll y){return ((x%MOD)*(y%MOD))%MOD;}
ll pwr(ll x, ll y){
if(y == 0) return 1;
ll ret = pwr(x, y/2);
ret = mul(ret, ret);
return (y & 1) ? mul(ret, x) : ret;
}
ll dvi(ll x, ll y){return mul(x, pwr(y, MOD-2));}
ll f(ll x){return dvi(mul(x, x+1), 2);}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(ll i = 1; i <= n; i++) cin >> a[i];
for(ll i = 1; i <= n; i++){
cin >> b[i];
pf[i] = pf[i-1] + b[i];
}
ll ans = 0;
for(ll i = 1; i <= n+1; i++){
while(!v.empty()){
if(a[v.back()] < a[i]) break;
ll h = a[v.back()], tes = a[i];
ll w = pf[i-1];
if(v.size() >= 2){
tes = max(tes, a[v.end()[-2]]);
w -= pf[v.end()[-2]];
}
// cout << h << "," << tes << " " << w << " << " << mul(sub(f(h), f(tes)), f(w)) << endl;
ans = sum(ans, mul(sub(f(h), f(tes)), f(w)));
v.pop_back();
}
v.push_back(i);
}
cout << ans << endl;
}
# | 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... |