# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
963079 | anton | Fancy Fence (CEOI20_fancyfence) | C++17 | 19 ms | 3184 KiB |
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 pii pair<int,int>
const int MAX_N = 1e5+1;
const int mod =1e9+7;
int h[MAX_N];
int w[MAX_N];
int nbp(int u){
return (u*(u+1LL)/2LL)%mod;
}
struct stak{
int s =0;
vector<pii> st;
stak(){
st.push_back({0, 0});
}
void insert(pii val){
while(st.back().second>=val.second){
auto e= st.back();
val.first+=e.first;
s = (s+mod-(nbp(e.second)*e.first)%mod)%mod;
st.pop_back();
}
s =(s+nbp(val.second)*val.first)%mod;
st.push_back(val);
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int sw = 0;
vector<pair<int, int>> ev;
for(int i = 0; i<n; i++){
cin>>h[i];
}
for(int i = 0; i<n; i++){
cin>>w[i];
}
int res= 0;
auto s = stak();
for(int i = 0; i<n; i++){
res = (res+ (nbp(w[i]) * nbp(h[i]))%mod)%mod;
s.insert({0, h[i]});
res = (res + (w[i]*s.s)%mod)%mod;
s.insert({w[i], h[i]});
}
cout<<res<<endl;
}
Compilation message (stderr)
# | 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... |