Submission #972137

#TimeUsernameProblemLanguageResultExecution timeMemory
972137Halym2007Fancy Fence (CEOI20_fancyfence)C++17
100 / 100
27 ms6872 KiB
#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<ll,ll>
#define ff first
#define ss second
#define sz size()

const int N = 2e5 + 1;

using namespace std;

ll n, a[N], b[N], mod = 1e9+7, ins = 5e8+4, sum;

vector <pii> v;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    v.pb({0,0});
    n++;
    for(int i = 1; i <= n; i++){
        ll w = 0;
        while(a[i] < v.back().ff){
            ll h_yzdaky = max(a[i],v[(int)v.sz-2].ff);
            ll h_aralyk = v.back().ff - h_yzdaky;
            w += v.back().ss;
            w %= mod;
            sum += w*(w+1) % mod * ins % mod * h_aralyk % mod * h_yzdaky % mod;
            sum %= mod;
            sum += w*(w+1) % mod * ins % mod * h_aralyk % mod * (h_aralyk+1) % mod * ins % mod;
            sum %= mod;
            v.pop_back();
        }
        if(v.back().ff == a[i]) v.back() = {a[i],b[i]+w+v.back().ss};
        else v.pb({a[i],b[i]+w});
    }
    cout << sum << '\n';
}
#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...