Submission #585787

#	Time	Username	Problem	Language	Result	Execution time	Memory
585787		MohamedFaresNebili	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	29 ms	5440 KiB

fancyfence

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
        using namespace std;
 
        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;
 
        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        #define int ll
 
        const int MOD = 1000 * 1000 * 1000 + 7;
 
        int N, X[100001], Y[100001];
 
        int solve(int A) {
            return ((A * (A + 1ll)) / 2ll) % MOD;
        }
        int solve(int A, int B) {
            return (solve(A) * solve(B)) % MOD;
        }
 
		int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N;
            for(int l = 0; l < N; l++) cin >> X[l];
            for(int l = 0; l < N; l++) cin >> Y[l];
            int res = 0, temp = 0; stack<pair<int, int>> S;
            for(int l = 0; l < N; l++) {
                int H = X[l], W = Y[l];
                res = (res + solve(H, W)) % MOD;
                int K = 0;
                while(!S.empty() && S.top().ff >= H) {
                    K = (K + S.top().ss) % MOD;
                    temp -= ((solve(S.top().ff) % MOD) * S.top().ss) % MOD;
                    if(temp < 0) temp += MOD;
                    W = (W + S.top().ss) % MOD;
                    S.pop();
                }
                res = ((res + ((Y[l] * K) % MOD) * solve(H))) % MOD;
                res = (res + (temp * Y[l])) % MOD;
                S.push({H, W});
                temp = (temp + (solve(H) * (W)) % MOD) % MOD;
            }
            cout << res % MOD << "\n";
            return 0;
		}

• 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