제출 #998831

#제출 시각아이디문제언어결과실행 시간메모리
998831TrustfulcomicFancy Fence (CEOI20_fancyfence)C++14
100 / 100
77 ms6088 KiB
#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
typedef long long ll;
typedef pair<ll,ll> pii;

ll count_rect(pii a){
    return ((a.first+1)*(a.first)/2%mod)*((a.second+1)*(a.second)/2%mod)%mod;
}

pii merge(ll& result, pii& a, pii b){
    if (a.first >= b.first){
        result += count_rect(a) - count_rect({b.first, a.second});
        result %= mod;
        return {b.first, (a.second+b.second)%mod};
    } else {
        result += count_rect(b) - count_rect({a.first, b.second});
        result %= mod;
        return {a.first, (a.second+b.second)%mod};
    }
}

int main(){
    int n; cin >> n;
    vector<ll> vysky(n+1, 0);
    vector<ll> sirky(n+1, 0);
    for (int i = 0 ;i<n; i++) cin >> vysky[i];
    for (int i = 0; i<n; i++) cin >> sirky[i];

    vector<pii> stc;
    stc.push_back({-1,-1}); 
    stc.push_back({vysky[0], sirky[0]});

    ll result = 0;

    for (int i = 1; i<n+1; i++){
        if (vysky[i] > stc.back().first){
            stc.push_back({vysky[i],sirky[i]});
        } else {
            while (stc[stc.size()-2].first >= vysky[i]){
                pii novy = merge(result, stc[stc.size()-2], stc[stc.size()-1]);
                stc.pop_back(); stc.pop_back();
                stc.push_back(novy);
            }
            if (vysky[i] > stc.back().first){
                stc.push_back({vysky[i], sirky[i]});
            } else {
                pii novy = merge(result, stc.back(), {vysky[i], sirky[i]});
                stc.pop_back();
                stc.push_back(novy);
            }
        }
    }

    cout << (result+mod)%mod << endl;
}
#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...