Submission #464294

#	Time	Username	Problem	Language	Result	Execution time	Memory
464294		osmanallazov	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	117 ms	5392 KiB

fancyfence

#include <bits/stdc++.h>
#define DIM 100010
#define MOD 1000000007
using namespace std;
long long h[DIM],w[DIM];
deque<pair <long long,long long> > d;
int n,i;
int main (){
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>h[i];
    for (i=1;i<=n;i++)
        cin>>w[i];
    n++; 
    d.push_back(make_pair(0,0));
    long long sol = 0;
    for (i=1;i<=n;i++){
        long long latime = 0;
        while (!d.empty() && h[i] < d.back().first){
            long long h_ant = max (h[i],d[d.size()-2].first);
            long long dif = (d.back().first - h_ant + MOD) % MOD;
            latime = (latime + d.back().second) % MOD;
            sol += ( dif * (dif + 1) / 2 % MOD + dif * h_ant % MOD) % MOD * (1LL * latime * (latime+1) / 2 % MOD) % MOD;
            sol %= MOD;
            d.pop_back();
        }
        w[i] = (w[i] + latime) % MOD;
        if (h[i] == d.back().first)
            d.back().second = (d.back().second + w[i]) % MOD;
        else d.push_back(make_pair(h[i],w[i]));
    }
    cout<<(sol+MOD)%MOD;
    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