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"
#define ll long long int
#define pb push_back
#define pii pair<ll,ll>
#define ff first
#define ss second
#define sz size()
const int N = 2e5 + 1;
using namespace std;
ll n, a[N], b[N], mod = 1e9+7, ins = 5e8+4, sum;
vector <pii> v;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
v.pb({0,0});
n++;
for(int i = 1; i <= n; i++){
ll w = 0;
while(a[i] < v.back().ff){
ll h_yzdaky = max(a[i],v[(int)v.sz-2].ff);
ll h_aralyk = v.back().ff - h_yzdaky;
w += v.back().ss;
w %= mod;
sum += w*(w+1) % mod * ins % mod * h_aralyk % mod * h_yzdaky % mod;
sum %= mod;
sum += w*(w+1) % mod * ins % mod * h_aralyk % mod * (h_aralyk+1) % mod * ins % mod;
sum %= mod;
v.pop_back();
}
if(v.back().ff == a[i]) v.back() = {a[i],b[i]+w+v.back().ss};
else v.pb({a[i],b[i]+w});
}
cout << sum << '\n';
}
# | 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... |