Submission #1019345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019345		DobromirAngelov	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	4 ms	8844 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;

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)/2)%MOD*(h*(h+1)/2)%MOD)%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));
        if(cur.fi!=1 || cur.se!=n) 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

*/

Compilation message (stderr)

fancyfence.cpp: In function 'void calc(long long int)':
fancyfence.cpp:77:43: warning: division by zero [-Wdiv-by-zero]
   77 |         if(cur.fi!=1 || cur.se!=n) cout<<1/0<<endl;
      |                                          ~^~

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