Submission #1209780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209780		cpdreamer	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	28 ms	4424 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;
#define P pair
#define F first
#define S second
#define pb push_back
#define V vector

void file() {
    freopen("input.txt.txt", "r", stdin);
    freopen("output.txt.txt", "w", stdout);
}

// Safe modulo
ll md(ll x) {
    return ((x % MOD) + MOD) % MOD;
}

// Safe multiplication
ll mul(ll a, ll b) {
    return md(md(a) * md(b));
}

// Sum of first a natural numbers mod MOD
ll g(ll a) {
    if (a % 2 == 0) {
        ll x = a / 2;
        return mul(x, a + 1);
    } else {
        ll x = (a + 1) / 2;
        return mul(a, x);
    }
}

ll f(ll a, ll b) {
    return mul(g(a), g(b));
}

void solve() {
    int n;
    cin >> n;
    vector<ll> h(n), w(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> w[i];

    ll ans = 0, c = 0;
    for (int i = 0; i < n; i++) {
        ans = md(ans + f(h[i], w[i]));
    }

    stack<P<P<ll, ll>, ll>> st;
    st.push({{0LL, 0LL}, 0LL});

    for (int i = 0; i < n; i++) {
        ll s = 0;
        while (h[i] < st.top().F.F) {
            ll height = st.top().F.F;
            ll width = st.top().F.S;
            ll sumS = st.top().S;

            s = md(s + width);
            c = md(c - mul(g(height), width));
            ans = md(ans + mul(c, width));
            c = md(c - mul(g(height), sumS));
            s = md(s + sumS);

            st.pop();
        }

        c = md(c + mul(md(s + w[i]), g(h[i])));
        st.push({{h[i], w[i]}, s});
    }

    while (st.size() > 1) {
        ll height = st.top().F.F;
        ll width = st.top().F.S;
        ll sumS = st.top().S;

        c = md(c - mul(g(height), width));
        ans = md(ans + mul(c, width));
        c = md(c - mul(g(height), sumS));

        st.pop();
    }

    cout << md(ans) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //file();
    solve();
    return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'void file()':
fancyfence.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("input.txt.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("output.txt.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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