Submission #998835

#	Time	Username	Problem	Language	Result	Execution time	Memory
998835		Trustfulcomic	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	17 ms	4212 KiB

fancyfence

#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){
        pii tmp = {b.first, a.second};
        result += count_rect(a) - count_rect(tmp);
        result %= mod;
        return {b.first, (a.second+b.second)%mod};
    } else {
        pii tmp = {a.first, b.second};
        result += count_rect(b) - count_rect(tmp);
        result %= mod;
        return {a.first, (a.second+b.second)%mod};
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    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 tmp = {vysky[i], sirky[i]};
                pii novy = merge(result, stc.back(), tmp);
                stc.pop_back();
                stc.push_back(novy);
            }
        }
    }

    cout << (result+mod)%mod << endl;
}

• 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