Submission #1008868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008868		kebine	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	10 ms	600 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 root[cnst];

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

int merge(int x, int y) {
    return root[find(x)] = find(y);
}

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];
    int count[n+5];
    int L[n+5];
    int R[n+5];
    memset(count, 0, sizeof(count));
    memset(vis, 0, sizeof(vis));

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

    for(auto [h, w, id]: vec) {
        count[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(count[id-1], w), A(count[id+1], w)), M(w, w))));

            count[L[id-1]] += count[L[id+1]]+w;
            count[R[id+1]] += count[R[id-1]]+w;
            R[L[id-1]] = R[id+1];
            L[R[id+1]] = L[id-1];
        }
        else if(vis[id-1] && id != 1) {
            R[L[id-1]] = id;
            L[id] = L[id-1];

            ans = A(ans, M(M(w, count[id-1]), h*(h+1)/2));

            count[L[id]] += count[id];
            count[id] = count[L[id]];

        }  
        else if(vis[id+1] && id != n) {
            L[R[id+1]] = id;
            R[id] = R[id+1];
            // cerr << L[id] << " " << R[id] << endl;

            ans = A(ans, M(M(w, count[id+1]), h*(h+1)/2));

            count[R[id]] += count[id];
            count[id] = count[R[id]];
        }
        // 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: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27