제출 #1367579

#제출 시각아이디문제언어결과실행 시간메모리
1367579yeulerFancy Fence (CEOI20_fancyfence)C++20
15 / 100
24 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;
const ll invm = 500000004;
vector<ll> hi(1e5+69), wi(1e5+69);

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

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;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…