Submission #398187

#	Time	Username	Problem	Language	Result	Execution time	Memory
398187		illyakr	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	107 ms	20848 KiB

fancyfence

#include <iostream>
#define int long long

using namespace std;
const int mod = 1000000007;

int n;
int h[101010], w[101010];
int RMQ[30][101010];
int L[101010];
int pref[101010];

int get(int l, int r) {
    int x = L[r - l + 1];
    int f = RMQ[x][l], s = RMQ[x][r - (1 << x) + 1];
    if (h[f] <= h[s]) return f;
    return s;
}
int res = 0;

void rec(int l, int r, int nowH) {
    if (l > r)return;
    int go = get(l, r);
    int H = h[go] - nowH;
    int W = pref[r] - pref[l - 1];
    H %= mod; W %= mod;
    res += (((((W * (W + 1)) / 2) % mod) *
             (((H * (H + 1)) / 2) % mod)) % mod);
    res %= mod;
    res += (((((((W * (W + 1)) / 2) % mod) * H) % mod) * nowH) % mod);
    res %= mod;

//    cout << l << " " << r << " << " << endl;

    rec(l, go - 1, h[go]); rec(go + 1, r, h[go]);
    return;
}

int32_t main()
{
    cin >> n;
    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++) {
        pref[i] = pref[i - 1] + w[i];
    }

    L[1] = 0;
    for (int i = 2; i <= n; i++) L[i] = L[i / 2] + 1;
    for (int i = 1; i <= n; i++) RMQ[0][i] = i;
    for (int i = 1; i <= L[n]; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            if (h[RMQ[i - 1][j]] <= h[RMQ[i - 1][j + (1 << (i - 1))]])
                RMQ[i][j] = RMQ[i - 1][j];
            else
                RMQ[i][j] = RMQ[i - 1][j + (1 << (i - 1))];
        }
    }
    rec(1, n, 0);
    cout << res;
}

• 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