Submission #1100881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100881		Owstin	Fancy Fence (CEOI20_fancyfence)	C++17	25 / 100	23 ms	5484 KiB

fancyfence

#include <bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define MOD (ll)(1e9 + 7)
void solve() {
    int b; cin >> b;
    vector<ll> heights(b);
    vector<pair<ll, ll>> width(b);
    for (int i = 0; i < b; i++){
        cin >> heights[i];
    }
    for (int i = 0; i < b; i++){
        ll x; cin >> x;
        if (i == 0){
            width[i] = {0, x - 1};
        }
        else{
            width[i].first = width[i - 1].second + 1;
            width[i].second = width[i].first + x - 1;
        }
    }
    stack<int> s1; stack<int> s2;
    vector<ll> widths(b);
    vector<ll> next(b);
    for (int i = 0; i < b; i++){
        while (!s1.empty() && heights[s1.top()] >= heights[i]){
            if (heights[s1.top()] == heights[i]){
                next[i] = heights[i];
            }
            s1.pop();
        }
        if (!s1.empty()) {
            next[i] = max(next[i], heights[s1.top()]);
        }
        widths[i] += width[i].second - (s1.empty() ? -1 : width[s1.top()].second);
        s1.push(i);
    }
    for (int i = b - 1; i >= 0; i--){
        while (!s2.empty() && heights[s2.top()] >= heights[i]){
            s2.pop();
        }
        if (!s2.empty()) {
            next[i] = max(next[i], heights[s2.top()]);
        }
        widths[i] += (s2.empty() ? width.back().second : width[s2.top()].first - 1) - width[i].second;
        s2.push(i);
    }
    ll res = 0;
    for (int i = 0; i < b; i++){
        widths[i] %= MOD;
        ll tall = (((heights[i] * (heights[i] + 1) / 2) % MOD) -
                ((next[i] % MOD * (next[i] + 1) % MOD / 2) % MOD) + MOD) % MOD;
        ll wide = (widths[i] * (widths[i] + 1) / 2) % MOD;
        res = (res + ((tall * wide) % MOD)) % MOD;
    }
    cout << res;
}
int main() {
    FAST_IO;
    //freopen(R"(C:\Users\caoji\Downloads\prime_subtractorization_input\prime_subtractorization_input.txt)", "r", stdin);
    //freopen("art2.in", "r", stdin);
    //freopen("art2.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

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