Submission #975289

#	Time	Username	Problem	Language	Result	Execution time	Memory
975289		efedmrlr	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	26 ms	7584 KiB

fancyfence

#include <bits/stdc++.h>

#define int long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;

int add(int x, int y) {
    if(x + y >= MOD) return x + y - MOD;
    return x + y;
}
int mult(int x, int y) {
    return (int)((1ll * x * y) % MOD);
}
int c2(int x) {
    return (int)((1ll * x * (x - 1) / 2) % MOD);
}
int subt(int x, int y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
void solve() {
    int n;
    cin >> n;
    vector<int> h(n + 1, 0), w(n + 1, 0), dp(n + 1, 0), p(n + 1, 0);
    vector<int> last(n + 1, 0);
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for(int i = 1; i <= n; i++) {
        p[i] = add(p[i - 1] , w[i]);
    }
    vector<int> stck;
    stck.pb(0);
    for(int i = 1; i <= n; i++) {
        while(stck.size() && h[i] < h[stck.back()]) {
            stck.pop_back();
        }
        assert(stck.size());
        last[i] = stck.back();
        stck.pb(i);
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << last[i] << " ";
    // }
    // cout << "\n";
    for(int i = 1; i <= n; i++) {
        dp[i] = add(dp[last[i]], mult(subt(p[i] , p[last[i]]), c2(h[i] + 1) ));
        int cont = mult(dp[last[i]], w[i]);
        cont = add(cont, mult( subt(p[i - 1], p[last[i]]), mult(w[i], c2(h[i] + 1) ) ) );
        cont = add(cont, mult(c2(w[i] + 1), c2(h[i] + 1)));
        ans = add(ans, cont);  
        // cout << "i:" << i << " dp:" << dp[i] << "\n"; 
        // cout << "cont:" << cont << "\n";
    }
    cout << ans << "\n";
    
}

signed main() {
    fastio();
    solve();
}

• 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