oj.uz

Submission #442784

# Submission time Handle Problem Language Result Execution time Memory
442784 2021-07-09T04:45:10 Z flashhh Fancy Fence (CEOI20_fancyfence) C++14
55 / 100
 89 ms 14916 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];
    return w[r]-w[l-1];
}

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; if (f[i]>=oo) f[i]-=oo;
        f[i] = f[i] + g[l] * range(i,i) %oo; if (f[i]>=oo) f[i]-=oo;
        
        g[i] = g[i] + cal(1,h[i]) * range(l+1,i) %oo; if (g[i]>=oo) g[i]-=oo;
        g[i] = g[i] + g[l]; if (g[i]>=oo) g[i]-=oo;
    }
    
    int res=0;
    for (int i=1;i<=n;++i)
    {
        res+=f[i];
        if (res>=oo) res-=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 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 36 ms 7156 KB Output is correct
4 Correct 85 ms 13956 KB Output is correct
5 Correct 88 ms 13936 KB Output is correct
6 Correct 86 ms 13952 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 7 ms 1676 KB Output is correct
3 Correct 36 ms 7488 KB Output is correct
4 Correct 84 ms 14776 KB Output is correct
5 Correct 86 ms 14852 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 7 ms 1744 KB Output is correct
4 Correct 37 ms 7528 KB Output is correct
5 Correct 81 ms 14652 KB Output is correct
6 Correct 85 ms 14916 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 7 ms 1816 KB Output is correct
9 Correct 39 ms 7504 KB Output is correct
10 Correct 89 ms 14596 KB Output is correct
11 Correct 88 ms 14696 KB Output is correct
12 Correct 1 ms 324 KB Output is correct

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