oj.uz

Submission #442781

# Submission time Handle Problem Language Result Execution time Memory
442781 2021-07-09T04:09:39 Z flashhh Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 2 ms 460 KB 
#include <bits/stdc++.h>
#define nmax 100010
#define ll long long

const int oo=1e9+7;

using namespace std;

int n,h[nmax],rmq[nmax][25];
ll f[nmax],g[nmax],w[nmax];

ll range(int l,int r)
{
    if (l==0) return w[r]%oo;
    return (w[r]-w[l-1])%oo;
}

ll get(int x,int y)
{
    int z=log2(y-x+1);
    return min(rmq[x][z],rmq[y-(1<<z)+1][z]);
}

ll cal(ll x,ll y)
{
    if (x>y) return 0;
    
    ll z=x+y; ll t=y-x+1;
    if (z%2==0) z/=2; else t/=2;
    z%=oo; t%=oo;
    
    return z*t%oo;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin>>n;
    for (int i=1;i<=n;++i) 
    {
        cin>>h[i];
        rmq[i][0]=h[i];
    }
    
    for (int i=1;i<=n;++i)
    {
        cin>>w[i];
        w[i]+=w[i-1];
    }
    
    for (int j=1;j<20;++j)
        for (int i=0;i<=n-(1<<j)+1;++i)
            rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    
    for (int i=1;i<=n;++i)
    {
        int l=0; int r=i-1;
        while (l<r)
        {
            int mid=(l+r+1)>>1;
            if (get(mid,i)<h[i]) l=mid;
            else r=mid-1;
        }
        
        f[i] = (f[i] + cal(1,h[i]) * cal(range(l+1,i-1)+1,range(l+1,i)) %oo) %oo;
        f[i] = (f[i] + g[l] * range(i,i) %oo) %oo;
        
        g[i] = (g[i] + cal(1,h[i]) * range(l+1,i) %oo) %oo;
        g[i] = (g[i] + g[l]) %oo;
    }
    
    int res=0;
    for (int i=1;i<=n;++i) res=(res+f[i])%oo;
    
    cout<<res;
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct