Submission #789389

#	Time	Username	Problem	Language	Result	Execution time	Memory
789389		JakobZorz	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	34 ms	17152 KiB

fancyfence

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1e9+7;
typedef pair<ld,ld> point;
//#define x first
//#define y second

int n;
ll w[100000],h[100000];
ll wsum[100001];
int hmin[100000][20];

int get_hmin(int l,int r){
    int width=r-l;
    int p=0;
    while((1<<p)<=width)
        p++;
    p--;
    
    int a=hmin[l][p];
    int b=hmin[r-(1<<p)][p];
    if(h[a]<h[b])
        return a;
    else
        return b;
}

ll get_combs(ll w,ll h){
    ll c1=w*(w+1)/2;
    c1%=MOD;
    ll c2=h*(h+1)/2;
    c2%=MOD;
    return(c1*c2)%MOD;
}

ll get(int l,int r,ll level){
    if(l==r)
        return 0;
    int m=get_hmin(l,r);
    ll width=(MOD+wsum[r]-wsum[l])%MOD;
    ll res=0;
    res+=get_combs(width,h[m]);
    res+=MOD-get_combs(width,level);
    res+=get(l,m,h[m]);
    res+=get(m+1,r,h[m]);
    return res%MOD;
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    //freopen("speeding.in","r",stdin);
    //freopen("speeding.out","w",stdout);
    
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];
    for(int i=0;i<n;i++)
        cin>>w[i];
    for(int i=0;i<n;i++)
        wsum[i+1]=(wsum[i]+w[i])%MOD;
    
    for(int i=0;i<n;i++)
        hmin[i][0]=i;
    for(int p=1;p<20;p++){
        for(int i=0;i<n;i++){
            int a=i;
            int b=i+(1<<(p-1));
            int c=i+(1<<p);
            if(c>n)
                break;
            if(h[hmin[a][p-1]]<h[hmin[b][p-1]])
                hmin[a][p]=hmin[a][p-1];
            else
                hmin[a][p]=hmin[b][p-1];
        }
    }
    
    cout<<get(0,n,0)<<"\n";
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27