Submission #1222386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222386		yassia	Fancy Fence (CEOI20_fancyfence)	C++20	58 / 100	17 ms	5056 KiB

fancyfence

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
#define int ll
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
using hash_map =gp_hash_table<int, int>;
using hash_set= gp_hash_table <int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
typedef tree<ll, null_type, less<>, rb_tree_tag,
        tree_order_statistics_node_update> ord_set;
const ll mod = 1e9+7;
ll add(ll a, ll b){
    return (((a%mod)+(b%mod))%mod);
}
ll sub(ll a, ll b) {
    return add(a, mod-(b%mod));
}
ll mult(ll a, ll b){
    return ((a%mod)*(b%mod))%mod;
}
ll pow_(ll e, ll n) {
    ll i = 1;
    while (n){
        if (n % 2) {
            i = mult(e, i);
        }
        e = mult(e, e);
        n /= 2;
    }
    return i;
}
ll inv2;
ll dv_2(ll a){
    return mult(a, inv2);
}
void solve1(){
   inv2 = pow_(2, mod-2);
   ll n;
   cin >> n;
   vector<ll> h(n);
   vector<ll> w(n);
   for (int i =0; i < n; i++){
       cin>>h[i];
   }
   for (int i =0; i < n; i++){
       cin >> w[i];
   }
   vector<ll> lf(n);
   vector<ll> rg(n);
   vector<ll> st;
   for (int i = n-1; i >= 0; i--){
       while (!st.empty() && h[i] < h[st.back()]){
           st.pop_back();
       }
       if (st.empty()){
           rg[i] = n;
       }
       else rg[i] = st.back();
       st.push_back(i);
   }
   st.clear();
   for (int i = 0; i <n ; i++){
       while (!st.empty() && h[i]<=h[st.back()]){
           st.pop_back();
       }
       if (st.empty()){
           lf[i] = -1;
       }
       else lf[i] = st.back();
       st.push_back(i);
   }
    vector<ll> wsum(n+1);
   for (int i  =1; i<= n; i++){
       wsum[i] = wsum[i-1]+w[i-1];
       wsum[i]%=mod;
   }
   /*
   for (auto x: rg){
       cout<<x<<" ";
   }cout<<endl;
   for (auto x: lf){
        cout<<x<<" ";
    }*/
   ll ans = 0;
   for (int i = 0; i < n; i++){
        int H = h[i];
        int W = w[i];
        int left = lf[i]+1;
        int right = rg[i]-1;
        int w_lf = wsum[i] - wsum[left];
        int w_rg = wsum[right+1] - wsum[i+1];
        ll X = add(mult(w_lf, w_rg),add(mult(W, w_lf),mult(W, w_rg)));
        ans = add(ans, mult(dv_2(mult(H,H+1)),add(X, dv_2(mult(W, W+1))) ));
   }
   cout<<ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t = 1;

   while (t){
        solve1();
        t-=1;
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 18 / 18
• Subtask 7: 0 / 27