제출 #1327601

#제출 시각아이디문제언어결과실행 시간메모리
1327601sh_qaxxorov_571Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
16 ms3532 KiB
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

// n * (n + 1) / 2 hesaplayan yardımcı fonksiyon
ll count_sum(ll n) {
    n %= MOD;
    return n * (n + 1) % MOD * 500000004 % MOD; // 500000004, MOD'a göre 2'nin tersidir.
}

struct Section {
    ll h, w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<ll> h(N), w(N);
    for (int i = 0; i < N; i++) cin >> h[i];
    for (int i = 0; i < N; i++) cin >> w[i];

    stack<Section> s;
    ll total_ans = 0;

    for (int i = 0; i <= N; i++) {
        ll cur_h = (i == N) ? 0 : h[i];
        ll cur_w = (i == N) ? 0 : w[i];
        ll accumulated_w = 0;

        while (!s.empty() && s.top().h >= cur_h) {
            Section top = s.top();
            s.pop();

            // Yığının bir altındaki yüksekliği bul (yoksa 0)
            ll prev_h = s.empty() ? 0 : s.top().h;
            // cur_h ile prev_h arasındaki maksimum yüksekliği baz almalıyız
            ll bottom_h = max(cur_h, prev_h);

            // Bu aralıkta (top.h yüksekliğinde) oluşan yeni genişlik
            accumulated_w = (accumulated_w + top.w) % MOD;

            // Dikdörtgen sayısı = (Yükseklik kombinasyonu) * (Genişlik kombinasyonu)
            // Sadece top.h ile bottom_h arasındaki "yeni" yükseklik dilimlerini sayıyoruz
            ll h_choices = (count_sum(top.h) - count_sum(bottom_h) + MOD) % MOD;
            ll w_choices = count_sum(accumulated_w);

            total_ans = (total_ans + h_choices * w_choices) % MOD;
        }

        if (i < N) {
            s.push({cur_h, (accumulated_w + cur_w) % MOD});
        }
    }

    cout << total_ans << endl;

    return 0;
}
#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...