Submission #312555

#	Time	Username	Problem	Language	Result	Execution time	Memory
312555		Jarif_Rahman	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	94 ms	14952 KiB

fancyfence

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll m = 1e9 + 7;
ll ml(ll x){
    ll y = x+1;
    if(y%2 == 0) y/=2;
    else x/=2;
    x%=m;
    y%=m;
    return (x*y)%m;
}
ll sth(ll a, ll b){
    ll x = b-a;
    ll s1 = x+2*a+1;
    if(x%2==0) x/=2;
    else s1/=2;
    return (x*s1)%m;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector <ll> h(n), w(n);
    for(ll &x: h) cin >> x;
    for(ll &x: w) cin >> x;
    h.pb(0);
    vector <int> in(n+1), in2(n+1);
    stack <int> st;
    vector <ll> sum(n+1);
    for(int i = 0; i <= n; i++){
        if(st.empty()){
            st.push(i);
            continue;
        }
        ll s = 0;
        while(!st.empty() && h[st.top()] > h[i]){
            int x = st.top();
            st.pop();
            in[x] = i;
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();
    h.pop_back();
    h.insert(h.begin(), 0);
    for(int i = n; i >= 0; i--){
        if(st.empty()){
            st.push(i);
            continue;
        }
        ll s = 0;
        while(!st.empty() && h[st.top()] > h[i]){
            int x = st.top();
            st.pop();
            in2[x - 1] = i - 1;
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();
    h.erase(h.begin());
    ll ss = 0;
    sum[0] = 0;
    for(int  i = 0; i < n; i++){
        ss+=w[i];
        sum[i+1] = ss;
    }
    ll ans = 0;
    vector <tuple<ll, ll, ll>> v;
    set<tuple<ll, int, int>> vs;
    for(int i = 0; i < n; i++){
        vs.insert({h[i], in2[i]+1, in[i]});
    }

    for(auto tp: vs){
        ll ls = 0;
        ll hh, inx1, inx2;
        tie(hh, inx1, inx2) = tp;
        if(inx1 != 0) ls = max(ls, h[inx1-1]);
        if(inx2 < n) ls = max(ls, h[inx2]);
        v.pb({hh, sum[inx2] - sum[inx1], ls});
    }
    ll ls = 0;
    for(auto tp: v){
        ll a, b, c;
        tie(a, b, c) = tp;
        ans+=(ml(b)*sth(c, a));
        ans%=m;
    }
    cout << ans << "\n";
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:40:12: warning: unused variable 's' [-Wunused-variable]
   40 |         ll s = 0;
      |            ^
fancyfence.cpp:56:12: warning: unused variable 's' [-Wunused-variable]
   56 |         ll s = 0;
      |            ^
fancyfence.cpp:87:8: warning: unused variable 'ls' [-Wunused-variable]
   87 |     ll ls = 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