oj.uz

Submission #881385

# Submission time Handle Problem Language Result Execution time Memory
881385 2023-12-01T08:13:57 Z Alish Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 2 ms 2396 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);


ll mod = 1e9+7;

ll power(ll a, ll b){

    ll ans=1;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;

}


const int N = 1e5+23;
ll pref[N], L[N], R[N];
ll h[N];
ll H[N], W[N], w[N];
int n;
int m;

map<pll, int> vis;

ll C(ll n){
    return n*(n+1)%mod*power(2, mod-2)%mod;
}


int main()
{
    fast_io
    cin>>n;

    for (int i=1; i<=n; i++) cin>>h[i];
    for (int i=1; i<=n; i++) cin>>w[i];

    for (int i=1; i<=n+1; i++) pref[i]=pref[i-1]+w[i];


    vector<int> st;

    for (int i=1; i<=n; i++){
        while(!st.empty() && h[st.back()]>=h[i]) st.pop_back();

        if(!st.empty()) L[i]=st.back();
        st.pb(i);

    }
    st.clear();

    for (int i=n; i>0; i--){
        while(!st.empty() && h[st.back()]>=h[i]) st.pop_back();
        if(!st.empty()) R[i]=st.back();
        else R[i]=n+1;
        st.pb(i);
    }

    ll ans=0;
    for (int i=1; i<=n; i++){
        if(vis[{h[i], L[i]}]) continue;
        vis[{h[i], L[i]}]=1;
        ll tool=pref[R[i]-1]-pref[L[i]];
        ll r1=h[i]-max(h[R[i]], h[L[i]]);
        ll r2=max(h[R[i]], h[L[i]]);
        ans=(ans+(C(r1)%mod+ r1*r2%mod)%mod*C(tool)%mod)%mod;

    }

    cout<<ans<<endl;


}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -