제출 #896609

#제출 시각아이디문제언어결과실행 시간메모리
896609tsumondaiFancy Fence (CEOI20_fancyfence)C++14
100 / 100
23 ms5976 KiB
#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 ";
}

컴파일 시 표준 에러 (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); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...