oj.uz

Submission #609281

# Submission time Handle Problem Language Result Execution time Memory
609281 2022-07-27T13:18:13 Z 1bin Fancy Fence (CEOI20_fancyfence) C++14
25 / 100
 16 ms 1876 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
const ll mod = 1e9 + 7;
ll n, h[NMAX], w[NMAX], ans, x, ix, mxh, wd;
stack<int> st;

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> w[i], w[i] = (w[i] + w[i - 1]) % mod;
    st.emplace(0);
    for(int i = 1; i <= n; i++){
        while(st.size() >= 2 && h[st.top()] > h[i]){
            ix = st.top(); st.pop();
            mxh = max(h[st.top()], h[i]);
            x = h[ix] - mxh;
            wd = w[ix] - w[st.top()]; wd = (wd % mod + mod) % mod;
            ans += (x * (x + 1) / 2 + x * mxh) % mod * wd * (wd + 1) / 2; ans %= mod;
            if(h[st.top()] > h[i]) w[st.top()] = w[ix];
        }
        if(h[st.top()] == h[i]) st.pop();
        st.emplace(i);
    }
    
    while(st.size() >= 2){
        ix = st.top(); st.pop();
        x = h[ix] - h[st.top()];
        wd = w[n] - w[st.top()]; wd = (wd % mod + mod) % mod;
        ans += (x * (x + 1) / 2 + x * h[st.top()]) % mod * wd * (wd + 1) / 2; ans %= mod;
    }
    cout << ans;
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 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 0 ms 212 KB Output is correct
2 Correct 0 ms 276 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 1076 KB Output is correct
4 Correct 15 ms 1796 KB Output is correct
5 Correct 15 ms 1876 KB Output is correct
6 Correct 16 ms 1832 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 212 KB Output is correct
2 Incorrect 1 ms 340 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 212 KB Output is correct
2 Incorrect 1 ms 340 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 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -