Submission #945716

#TimeUsernameProblemLanguageResultExecution timeMemory
945716WongYiKaiFancy Fence (CEOI20_fancyfence)C++14
100 / 100
24 ms6492 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; ll m = 1000000007; cin >> n; ll h[n+5],w[n+5]; ll prefw[n+5]; ll w2 = 0; for (int i=0;i<n;i++){ ll temp; cin >> temp; h[i] = temp; } for (int i=0;i<n;i++){ ll temp; cin >> temp; w[i] = temp; w2 += temp; //w2%=m; prefw[i] = w2; } stack<pair<ll,ll>> s; ll total=0; for (int i=0;i<n;i++){ ll num=0; ll carry=0; while (!s.empty() && h[s.top().first]>h[i]){ s.pop(); } if (!s.empty()){ carry += s.top().second; carry%=m; //cout << carry << " "; ll height = h[i]; ll width = prefw[i]-prefw[s.top().first]-w[i]; width%=m; height = height*(height+1)/2; height%=m; carry += (height*width)%m; carry%=m; } else{ ll height = h[i]; ll width = prefw[i]-w[i]; width%=m; height = height*(height+1)/2; height%=m; carry += (height*width)%m; carry%=m; } //cout << carry << " "; ll height = h[i]; ll width = w[i]; num += (carry*width)%m; num%=m; height = height*(height+1)/2; ll w2 = width*(width+1)/2; height%=m; w2%=m; num += (height*w2)%m; num%=m; carry += (height*width)%m; carry%=m; //cout << i << " " << carry << "\n"; s.push({i,carry}); total += num; total %=m; } cout << total%m; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...