Submission #1367573

#TimeUsernameProblemLanguageResultExecution timeMemory
1367573yeulerFancy Fence (CEOI20_fancyfence)C++20
15 / 100
22 ms1860 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pii pair<int, int>
#define pl pair<ll, ll>
#define kagamine_len ios_base::sync_with_stdio(0); cin.tie(0);
#define file_in freopen("input.txt", "r", stdin);
#define file_out freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()

using namespace std;

/*

g++ -std=c++20 CEOI2020_Fancy_Fence.cpp -o output/CEOI2020_Fancy_Fence.exe
./output/CEOI2020_Fancy_Fence.exe

*/

const ll mod = 1e9+7;
vector<ll> hi(1e5+69), wi(1e5+69);

ll solve(int l, int r){
    if (l > r) return 0;
    if (l == r){
        __int128_t res = ((wi[l] * (wi[l]+1) / 2) % mod) * ((hi[l] * (hi[l]+1) / 2) % mod) % mod;
        return (ll)res;
    }
    int mid = (l+r)/2;
    __int128_t le = solve(l, mid), ri = solve(mid+1, r);
    __int128_t res = 0, lenl = 0, lenr = 0, curh = 2e18;
    for (int i = l; i <= r; i++) curh = min((__int128_t)hi[i], curh);
    for (int i = l; i <= mid; i++) lenl = (wi[i] + lenl) % mod;
    for (int i = mid+1; i <= r; i++) lenr = (wi[i] + lenr) % mod;
    res = ((lenl * lenr % mod) * (curh*(curh+1)/2)) % mod;
    res = ((res + le) % mod + ri) % mod;
    return (ll)res;
}

int main(){
    kagamine_len
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> hi[i];
    for (int i = 1; i <= n; i++) cin >> wi[i];
    ll ans = solve(1, n);
    cout << ans << "\n";
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...