Submission #694733

#	Time	Username	Problem	Language	Result	Execution time	Memory
694733		hgmhc	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	40 ms	5800 KiB

fancyfence

#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;
      |                ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27