제출 #1352094

#제출 시각아이디문제언어결과실행 시간메모리
1352094nikaa123Fancy Fence (CEOI20_fancyfence)C++20
12 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(), (x).end()
#define deb(x) cout << #x << "-" << x << endl
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef string str;
typedef long long ll;
typedef __int128_t int128;
typedef vector<int> vii;
typedef pair<int, int> pii;
typedef tuple<int,int,int> tpii;
 
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1000000007;
const int mod67 = 676767677;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const long double PI = 2 * acos(0.0);
 
const int N = 2e5+5;

inline void test_case() {
    
    int n;
    cin >> n;
    vii h(n+1,0);
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    vii w(n+1,0);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    vector <tuple<int,int,int>> v;
    for (int i = 1; i <= n; i++) {
        v.eb(h[i],w[i],i);
    } 
    sort(all(v),greater<tuple<int,int,int>>());
    vii par(n+1,0);
    vii sum(n+1,0);
    for (int i = 1; i <= n; i++) {
        sum[i] = w[i];
    }
    iota(all(par),0);
    function<int(int)> getpar = [&](int x) {
        if (par[x] == x) return x;
        return par[x] = getpar(par[x]);
    };
    auto unionset = [&](int a, int b) {
        a = getpar(a);
        b = getpar(b);
        if(a == b) return;
        par[a] = b;
        sum[b] += sum[a];
    };
    vii fix(n+2,0);
    int ans = 0;
    for (auto [h,w,i]:v) {
        int a = 0;
        int b = 0;
        if (fix[i-1]) {
            a = sum[getpar(i-1)];
            unionset(i,i-1);
        }
        if (fix[i+1]) {
            b = sum[getpar(i+1)];
            unionset(i,i+1);
        }
        int ds = (h*(h+1)/2) % MOD;
        int res = ((a+b)*w + a*b) % MOD;
        res = (res * ds) % MOD;
        ans = (ans + res) % MOD;
        // deb(a);
        // deb(b);
        // deb(res);
        fix[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int res = (h[i]*(h[i]+1)/2) % MOD;
        int ds = (w[i]*(w[i]+1)/2) % MOD;
        res = (res * ds) % MOD;
        ans = (ans + res) % MOD;
        // deb(res);
    }
    cout << ans << endl;
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    while (T--) test_case();
    return 0;
}
#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...