제출 #1008879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008879		devariaota	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	45 ms	13516 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

const int mod = 1e9+7;

int F[cnst];
int inv[cnst];

int A(int a, int b) {return ((a%mod)+(b%mod))%mod;}
int S(int a, int b) {return ((a%mod)-(b%mod)+mod)%mod;}
int M(int a, int b) {return ((a%mod)*(b%mod))%mod;}

int E(int b, int p) {
    if(!p) return 1;
    return (p%2 ? M(E(M(b, b), p/2), b) : E(M(b, b), p/2));
}

int C(int n, int r) {return M(M(F[n], inv[n-r]), inv[r]);}

void prefac(int maxn) {
    F[0] = 1;
    for(int i = 1; i<=maxn; i++) F[i] = M(F[i-1], i);
    inv[maxn] = E(F[maxn], mod-2);
    for(int i = maxn-1; i>=0; i--) inv[i] = M(inv[i+1], i+1);
}

int gcd(int a, int b) {return b ? gcd(b, a%b): a;}
int lcm(int a, int b) {return M(a/gcd(a, b), b);}

int L[cnst];
int R[cnst];
int count1[cnst];
int root[cnst];

int find(int x) {return root[x] == x ? x : root[x] = find(root[x]);}

void merge(int x, int y) {
    int lx = L[find(x)];int ly = L[find(y)];
    int rx = R[find(x)];int ry = R[find(y)];
    int cx = count1[find(x)];int cy = count1[find(y)];
    root[find(x)] = find(y);

    L[find(x)] = min(lx, ly);
    R[find(x)] = max(rx, ry);
    count1[find(x)] = cx+cy;
}

void solve() {
    int n; cin >> n;

    int H[n+5];
    int W[n+5];

    for(int i = 1; i<=n; i++) cin >> H[i];
    for(int j = 1; j<=n; j++) cin >> W[j];

    int ans = 0;

    vector<tuple<int, int, int>> vec;
    for(int i = 1; i<=n; i++) vec.pb({H[i], W[i], i}), ans = A(ans, M(H[i]*(H[i]+1)/2, W[i]*(W[i]+1)/2));
    // for(int i = 1; i<=n; i++) cerr << H[i] << " " << W[i] << endl;

    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());

    bool vis[n+5];
    // memset(count, 0, sizeof(count));
    memset(vis, 0, sizeof(vis));

    for(int i = 1; i<=n; i++) L[i] = R[i] = root[i] = i;
    // cerr << ans << endl;

    for(auto [h, w, id]: vec) {
        count1[id] = w; vis[id] = 1;
        // mx[id] = h; tt[id] = M(h, w);
        // cerr << h << " " << w << " " << id << endl;
        // cerr << count[id-1] << " " << count[id] << " " << count[id+1] << endl;
        if(vis[id-1] && vis[id+1] && id != 1 && id != n) {
            ans = A(ans, M(h*(h+1)/2, S(M(A(count1[find(id-1)], w), A(count1[find(id+1)], w)), M(w, w))));
            merge(id, id-1);
            merge(id, id+1);
        }
        else if(vis[id-1] && id != 1) {
            ans = A(ans, M(M(count1[find(id)], count1[find(id-1)]), h*(h+1)/2));
            merge(id, id-1);
        }  
        else if(vis[id+1] && id != n) {
            ans = A(ans, M(M(count1[find(id)], count1[find(id+1)]), h*(h+1)/2));
            merge(id, id+1);
        }
        // for(int i = 1; i<=n; i++) cerr << count[i] << " "; cerr << endl;
        // cerr << ans << endl;
    }


    cout << ans%mod << endl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if(mutipletestcase) 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