Submission #1282476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282476		minhphan	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	11 ms	3908 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

constexpr int BUF_SZ = 1 << 15;

inline namespace Input {
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char() {
        if (pos == len) {
            pos = 0;
            len = static_cast<int>(fread(buf, 1, BUF_SZ, stdin));
            if (!len) { return EOF; }
        }
        return buf[pos++];
    }

    int read_int() {
        char ch;
        int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }
        }
        int x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
        return x * sgn;
    }
}

inline namespace Output {
    char buf[BUF_SZ];
    int pos;

    void flush_out() {
        fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

    void write_char(const char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;
    }

    void write_int(int x) {
        static char num_buf[100];
        if (x < 0) {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = static_cast<char>('0' + (x % 10)); }
        write_char(static_cast<char>('0' + x));
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');
    }

    void write_long_long(long long x) {
        static char num_buf[100];
        if (x < 0) {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = (char) ('0' + (x % 10)); }
        write_char((char) ('0' + x));
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');
    }

    // auto-flush output when the program exits
    void init_output() { assert(atexit(flush_out) == 0); }
}

constexpr int MOD = 1e9 + 7;

long long mul(const long long a, const long long b) {
    return (a % MOD)*(b % MOD) % MOD;
}

int main() {//TODO verstehen
    init_output();

    int n = read_int();

    vector<long long> height(n + 1, 0), width(n + 1, 0);
    vector<long long> prefixSum(n + 1, 0); //Summe von der Breite
    vector<long long> dp(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        height[i] = read_int();
    }
    for (int i = 1; i <= n; ++i) {
        width[i] = read_int();
        prefixSum[i] = (prefixSum[i - 1] + width[i]) % MOD;
    }

    // absteigende Höhe
    stack<int> monoStack;
    monoStack.push(0);

    long long answer = 0;

    for (int i = 1; i <= n; ++i) {
        while (monoStack.size() > 1 && height[monoStack.top()] >= height[i]) {
            monoStack.pop();
        }

        const int j = monoStack.top();

        // Summe der Breiten von (j+1) .. i
        const long long len = (prefixSum[i] - prefixSum[j] + MOD) % MOD;

        //Summe der Breiten außer der aktuellen
        const long long L1 = (len - width[i] % MOD + MOD) % MOD;

        const long long triHeight = mul( mul(height[i], height[i] + 1), 500000004);
        const long long triWidth = mul( mul(width[i], width[i] + 1), 500000004);

        //T_A,B
        const long long term1 = mul( mul(L1, triHeight), width[i] );
        const long long term2 = mul(triHeight, triWidth);
        const long long A = (term1 + term2) % MOD;

        const long long B = mul(dp[j], width[i]);

        dp[i] = ( dp[j] + mul(len, triHeight) ) % MOD;

        monoStack.push(i);

        answer = (answer + A + B) % MOD;
    }

    write_long_long(answer);

    return 0;
}

• 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