제출 #1334649

#제출 시각아이디문제언어결과실행 시간메모리
1334649ti24son_phFancy Fence (CEOI20_fancyfence)C++20
55 / 100
16 ms2768 KiB
#include <bits/stdc++.h>
using namespace std;
#define el '\n'
#define int long long
#define fi first
#define se second
#define sz(x) (int)(x).size()
const int maxn=1e5+5,mod=1e9+7;
int n,h[maxn],w[maxn]; bool checksub2=1,checksub3=1,checksub4=1,checksub5=1,checksub6=1;
namespace sub2{
    int res;
    void solve(){
        for (int l=1;l<=n;l++){
            int mn=1e18;
            for (int r=l;r<=n;r++){
                mn=min(mn,h[r]);
                int tmp1=mn,tmp2=mn+1;
                if (tmp1%2==0) tmp1/=2; else tmp2/=2;
                int c=tmp1*tmp2%mod;
                res=(res+c)%mod;
            }
        }
        cout<<res;
    }
}
namespace sub3{
    int tmp1,tmp2,add,res;
    void solve(){
        int M=0;
        for(int i=1;i<=n;i++) M+=w[i];
        tmp1=M,tmp2=M+1;
        if (tmp1%2==0) tmp1/=2; else tmp2/=2;
        int sum=(tmp1%mod)*(tmp2%mod)%mod;
        int cnt=0,cur=0;
        for (int i=1;i<=n;i++){
            if(h[i]==2) cur+=w[i];
            else{
                tmp1=cur,tmp2=cur+1;
                if (tmp1%2==0) tmp1/=2; else tmp2/=2;
                add=(tmp1%mod)*(tmp2%mod)%mod; cnt=(cnt+add)%mod;
                cur=0;
            }
        }
        if (cur){
            tmp1=cur,tmp2=cur+1;
            if (tmp1%2==0) tmp1/=2; else tmp2/=2;
            add=(tmp1%mod)*(tmp2%mod)%mod; cnt=(cnt+add)%mod;
        }
        res=(sum+2*cnt)%mod;
        cout<<res;
    }
}
namespace sub4{
    void solve(){
        int H=h[1],M=0;
        for (int i=1;i<=n;i++) M+=w[i];
        int tx1=M,tx2=M+1,ty1=H,ty2=H+1;
        if (tx1%2==0) tx1/=2; else tx2/=2;
        if (ty1%2==0) ty1/=2; else ty2/=2;
        int tmp1=(tx1%mod)*(tx2%mod)%mod,tmp2=(ty1%mod)*(ty2%mod)%mod;
        cout<<(tmp1*tmp2)%mod;
    }
}
namespace sub5{
    int suf[maxn],tmp1,tmp2,res;
    void solve(){
        for (int i=n;i>=1;i--) suf[i]=suf[i+1]+w[i];
        for (int i=1;i<=n;i++){
            int wi=w[i],hi=h[i];
            tmp1=wi,tmp2=wi+1;
            if (tmp1%2==0) tmp1/=2; else tmp2/=2;
            int val1=(tmp1%mod)*(tmp2%mod)%mod;
            int val2=(wi%mod)*(suf[i+1]%mod)%mod;
            int sum=(val1+val2)%mod;
            tmp1=hi,tmp2=hi+1;
            if (tmp1%2==0) tmp1/=2; else tmp2/=2;
            int cnt=(tmp1%mod)*(tmp2%mod)%mod;
            res=(res+sum*cnt)%mod;
        }
        cout<<res;
    }
}
namespace sub6{
    int pre[maxn],res,tmp1,tmp2;
    void solve(){
        for (int i=1;i<=n;i++) pre[i]=pre[i-1]+w[i];
        for (int l=1;l<=n;l++){
            int mn=1e18;
            for (int r=l;r<=n;r++){
                mn=min(mn,h[r]);
                int W=pre[r]-pre[l-1];
                tmp1=W,tmp2=W+1;
                if (tmp1%2==0) tmp1/=2; else tmp2/=2;
                int A=(tmp1%mod)*(tmp2%mod)%mod;
                tmp1=mn,tmp2=mn+1;
                if (tmp1%2==0) tmp1/=2; else tmp2/=2;
                int B=(tmp1%mod)*(tmp2%mod)%mod;
                res=(res+A*B)%mod;
            }
        }
        cout<<res;
    }
}
namespace sub7{
    int res,W,M,tmp1,tmp2,val1,val2;
    void solve(){
        ///Anh Khang béo vãi lồn
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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;i++){
        if (w[i]!=1) checksub2=0;
        if (!(h[i]==1||h[i]==2)) checksub3=0;
        if (i>1&&h[i]!=h[1]) checksub4=0;
        if (i<n&&h[i]>h[i+1]) checksub5=0;
    }
    if (n>50) checksub2=0; if (n>1000) checksub6=0;
    if (checksub2) sub2::solve();
    else if (checksub3) sub3::solve();
    else if (checksub4) sub4::solve();
    else if (checksub5) sub5::solve();
    else if (checksub6) sub6::solve();
    else sub7::solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...