Submission #972137

#	Time	Username	Problem	Language	Result	Execution time	Memory
972137		Halym2007	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	27 ms	6872 KiB

fancyfence

#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';
}

• 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