oj.uz

Submission #1019331

# Submission time Handle Problem Language Result Execution time Memory
1019331 2024-07-10T17:42:12 Z DobromirAngelov Fancy Fence (CEOI20_fancyfence) C++14
25 / 100
 19 ms 7384 KB 
#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));
    }
    ev.clear();
    //cout<<ans<<endl;
}

bool cmp(int x,int 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

*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 9 ms 3296 KB Output is correct
4 Correct 19 ms 7384 KB Output is correct
5 Correct 17 ms 5856 KB Output is correct
6 Correct 17 ms 7316 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -