Submission #1019355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019355		DobromirAngelov	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	48 ms	3520 KiB

fancyfence

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

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)
    {
        long long d=pref[cur.se]-pref[cur.fi-1];
        sum(ans, rect(d,h));
    }
    ev.clear();
}

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])
    {
        if(ind-1==last.se) last.se++, ev.back().se++;
        else addL(ind);
        changeRngL(ind);
    }
    if(ev.size()>0) last=ev.back();
    if(used[ind+1])
    {
        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);
    }

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

    used[ind]=1;
}
calc(h[ord[n-1]]);

cout<<ans<<endl;

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