Submission #694733

#TimeUsernameProblemLanguageResultExecution timeMemory
694733hgmhcFancy Fence (CEOI20_fancyfence)C++17
100 / 100
40 ms5800 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,a,b) for (auto i = (a); i <= (b); ++i) const int N = 100003, MOD = 1e9+7; int n; ll h[N], w[N], x[N], c[N], sum, ans; stack<int> s; ll C(ll n){return (n*(n-1)/2)%MOD;} int main() { scanf("%d", &n); rep(i,1,n) scanf("%lld", &h[i]); rep(i,1,n) scanf("%lld", &w[i]), x[i] = (x[i-1]+w[i])%MOD; rep(i,1,n) { while (not empty(s) and h[s.top()] > h[i]) sum = (sum-c[s.top()])%MOD, s.pop(); ans += (x[i-1]-(empty(s)?0:x[s.top()]))*C(h[i]+1)%MOD*w[i]%MOD; ans += sum*w[i]%MOD + C(w[i]+1)*C(h[i]+1)%MOD; ans %= MOD; c[i] = (x[i]-(empty(s)?0:x[s.top()]))*C(h[i]+1)%MOD; sum = (sum+c[i])%MOD; s.push(i); } printf("%lld\n",(ans%MOD+MOD)%MOD); }

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fancyfence.cpp:14:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     rep(i,1,n) scanf("%lld", &h[i]);
      |                ~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp:15:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     rep(i,1,n) scanf("%lld", &w[i]), x[i] = (x[i-1]+w[i])%MOD;
      |                ~~~~~^~~~~~~~~~~~~~~
#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...