Submission #448796

#	Time	Username	Problem	Language	Result	Execution time	Memory
448796		Aryan_Raina	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	49 ms	6268 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
#define all(a) a.begin(), a.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int INF = 1e12;
const int MOD = 1e9+7;
const int inv2 = 5e8+4;
  
struct UFDS {
    vector<int> p, wn;
    UFDS(int n) : p(n,-1), wn(n, 0) {}
    int fin(int v) { return p[v] < 0 ? v : p[v] = fin(p[v]); }
    bool join(int a, int b) {
        a = fin(a), b = fin(b);
        if (a == b) return false;
        if (-p[a] < -p[b]) swap(a, b);
        p[a] += p[b]; p[b] = a; (wn[a] += wn[b]) %= MOD;
        return true;
    }
};
 
void solve() {
    int N; cin >> N;
    vector<int> h(N), w(N);
    UFDS ufds(N);
    for (int &i : h) cin >> i;
    for (int &i : w) cin >> i;
    for (int i = 0; i < N; i++) ufds.wn[i] = w[i];
 
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) { return h[a] > h[b]; });
 
    int ans = 0;
    vector<bool> act(N, false);
    for (int x : order) {
        int lw = 0, rw = 0;
        if (x-1 >= 0 && act[x-1]) {
            lw = ufds.wn[ufds.fin(x-1)];
            ufds.join(x, x-1);
        }
        if (x+1 < N && act[x+1]) {
            rw = ufds.wn[ufds.fin(x+1)];
            ufds.join(x, x+1);
        }
 
        int a = (h[x] * (h[x] + 1) % MOD) * inv2 % MOD;
        int b = (w[x] * ufds.wn[ufds.fin(x)]) % MOD - ((w[x] - 1) * w[x] % MOD * inv2 % MOD);
        b = (b % MOD + MOD) % MOD;
 
        ans += (a * b % MOD) + ((lw * rw % MOD) * a % MOD) % MOD;
        ans %= MOD;
 
        act[x] = true;
    }
 
    ans = (ans + MOD) % MOD;
    cout << ans << '\n';
} 
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
 
    int t = 1; //cin >> t;
    while (t--) solve();   
}  

• 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