Submission #896609

#	Time	Username	Problem	Language	Result	Execution time	Memory
896609		tsumondai	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	23 ms	5976 KiB

fancyfence

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<ll, ll>
#define fi first
#define se second
#define bit(x, i) ((x >> i) & 1)
#define SZ(x) ((int)(x.size()))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define task "BRICKWALL"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }

const int MXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const int BASE = 3137;
const int BL = 320;

int n;
int l[MXN], r[MXN], st[MXN], top;
ll pre[MXN], h[MXN], w[MXN], ans;

ll getsum(int l, int r) {
    return (pre[r] - pre[l - 1] + MOD) % MOD;
}

ll T(ll a, ll b) {
    return (a * (a + 1) / 2 % MOD) * (b * (b + 1) / 2 % MOD) % MOD;
}

void solution() {
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) {
        cin >> w[i];
        pre[i] = (pre[i - 1] + w[i]) % MOD;
    }
    st[top = 0] = 0;
    FOR(i, 1, n) {
        while (top && h[st[top]] > h[i]) top--;
        l[i] = st[top] + 1;
        st[++top] = i;
    }
    st[top = 0] = n + 1;
    FORD(i, n, 1) {
        while (top && h[st[top]] >= h[i]) top--;
        r[i] = st[top] - 1;
        st[++top] = i;
    }

    FOR(i, 1, n) (ans += (h[i] * (h[i] + 1) / 2 % MOD) * (w[i] * (w[i] + 1) / 2 % MOD)) %= MOD;

    FOR(i, 1, n) {
        (ans += T(h[i], getsum(l[i], r[i]))) %= MOD;
        ans = (ans - T(h[i], getsum(l[i], i - 1)) + MOD) % MOD;
        ans = (ans - T(h[i], getsum(i + 1, r[i])) + MOD) % MOD;
        ans = (ans - T(h[i], w[i]) + MOD) % MOD;
    }
    cout << ans;
}

int32_t main() {
    if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
    ios::sync_with_stdio(0); cin.tie(0);
    int ntest = 1; //cin >> ntest;
    while (ntest--) solution();
    cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

Compilation message (stderr)

fancyfence.cpp: In function 'int32_t main()':
fancyfence.cpp:68:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:68:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "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