Submission #1019353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019353		DobromirAngelov	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	34 ms	7260 KiB

fancyfence

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define int long long

using namespace std;

const int MAXN=1e5+5;
const int MOD=1e9+7;
const int INV2SQ=250000002;

int n;
int h[MAXN];
int w[MAXN];
long long pref[MAXN];
int ord[MAXN];
bool used[MAXN];
vector<pair<int,int> > ev;
pair<int,int> rng[MAXN];
int ans=0;

int rect(long long w,long long h)
{
    w%=MOD;
    h%=MOD;
    return (((w*(w+1))%MOD)*((h*(h+1))%MOD)%MOD*INV2SQ)%MOD;
}

void sum(int &a,int val)
{
    a+=val;
    if(a>=MOD) a-=MOD;
}

void subtr(int &a,int val)
{
    a-=val;
    if(a<0) a+=MOD;
}

void addL(int ind)
{
    ev.push_back({rng[ind-1].fi, ind});
    long long d=pref[ind-1]-pref[rng[ind-1].fi-1];
    subtr(ans, rect(d,h[ind]));
}

void changeRngL(int ind)
{
    int l=rng[ind-1].fi;
    int r=rng[ind].se;
    rng[l]={rng[l].fi, rng[r].se};
    rng[r]={rng[l].fi, rng[r].se};
}

void addR(int ind)
{
    ev.push_back({ind, rng[ind+1].se});
    long long d=pref[rng[ind+1].se]-pref[ind];
    subtr(ans, rect(d,h[ind]));
}

void changeRngR(int ind)
{
    int l=rng[ind].fi;
    int r=rng[ind+1].se;
    rng[l]={rng[l].fi, rng[r].se};
    rng[r]={rng[l].fi, rng[r].se};
}

void calc(int h)
{
    for(auto cur: ev)
    {//cout<<"("<<cur.fi<<","<<cur.se<<")  ";
        long long d=pref[cur.se]-pref[cur.fi-1];
        sum(ans, rect(d,h));
        //cout<<1/0<<endl;
    }
    ev.clear();
    //cout<<ans<<endl;
}

bool cmp(int x,int y)
{
    if(h[x]==h[y]) return x<y;
    return h[x]>h[y];
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

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++) pref[i]=pref[i-1]+w[i];
for(int i=1;i<=n;i++) rng[i]={i,i};

iota(ord,ord+n,1);
sort(ord,ord+n,cmp);

for(int i=0;i<n;i++)
{
    if(i>0 && h[ord[i]]<h[ord[i-1]]) calc(h[ord[i-1]]);

    int ind=ord[i];

    pair<int,int> last({-1,-1});
    if(!ev.empty()) last=ev.back();

    if(used[ind-1])
    {//cout<<i<<" "<<ind<<" "<<last.fi<<" "<<last.se<<endl;
        if(ind-1==last.se) last.se++, ev.back().se++;
        else addL(ind);
        changeRngL(ind);
        //cout<<ans<<" "<<rng[ind].fi<<" "<<rng[ind].se<<endl;
    }
    if(ev.size()>0) last=ev.back();
    if(used[ind+1])
    {//cout<<i<<" "<<ind<<" "<<last.fi<<" "<<last.se<<endl;
        if(last.se==ind)
        {
            last.se=rng[ind+1].se; ev.back().se=rng[ind+1].se;
            long long d=pref[rng[ind+1].se]-pref[ind];
            subtr(ans, rect(d,h[ind]));
        }
        else addR(ind);
        changeRngR(ind);
        //cout<<ans<<" "<<rng[ind].fi<<" "<<rng[ind].se<<endl;
    }

    if(!used[ind-1] && !used[ind+1]) sum(ans, rect(w[ind], h[ind]));

    used[ind]=1;

    //cout<<i<<" "<<ord[i]<<": "<<ans<<endl;
}
calc(h[ord[n-1]]);

cout<<ans<<endl;

return 0;
}
/*
6
1 3 5 3 2 6
1 1 1 1 1 1

5
1 3 5 3 2
3 2 1 3 3

7
3 4 1 9 8 3 9
1 1 1 1 1 1 1

10
4 4 4 4 4 4 4 4 4 4
1 3 7 8 4 5 9 2 7 5

17
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
2 3 9 5 7 3 8 1 9 9 6 1 2 4 8 5 4

*/

• 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