#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int m=1e9+7;
int main(){
int n;
cin>>n;
long long int res=0;
vector<long long int>horizontales(n+1);
vector<long long int>alturas(n);
stack<int>pila1;
stack<int>pila2;
stack<int>pila3;
vector<pair<int,int>>siguiente(n, make_pair(-1, n));
vector<int>v(n, -1);
for (int i=0; i<n; i++) cin>>alturas[i];
horizontales[0]=0;
int x;
for (int i=0; i<n; i++){
cin>>x;
horizontales[i+1]=horizontales[i]+x;
}for (int i=0; i<n; i++){
while (!pila1.empty()){
if (alturas[pila1.top()]>=alturas[i]) pila1.pop();
else{
siguiente[i].first=pila1.top();
break;
}
}pila1.push(i);
while (!pila2.empty()){
if (alturas[pila2.top()]>=alturas[n-i-1]) pila2.pop();
else{
siguiente[n-i-1].second=pila2.top();
break;
}
}pila2.push(n-i-1);
while (!pila3.empty()){
if (alturas[pila3.top()]<=alturas[i]){
v[i]=pila3.top();
break;
}else pila3.pop();
}pila3.push(i);
}
int left=0, right, top, bottom=0;
long long int h, w;
for (int i=0; i<n; i++){
left=horizontales[i]-horizontales[siguiente[i].first+1];
right=horizontales[siguiente[i].second]-horizontales[siguiente[i].first+1];
top=alturas[i];
if (v[i]==-1) bottom=0;
else bottom=alturas[v[i]];
w=(right*(right+1)-left*(left+1))/2;
w%=m;
h=(top*(top+1)-bottom*(bottom+1))/2;
h%=m;
res+=(w*h)%m;
res%=m;
}cout<<res<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 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 |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 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 |
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 |
1 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |