Submission #881454

#	Time	Username	Problem	Language	Result	Execution time	Memory
881454		Danet	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	89 ms	6032 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

#define tof_io  ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define double  long double
#define int     long long
#define pb      push_back
#define all(x)  x.begin(),x.end()
#define endl    '\n'

const int mod = 1e9+7; //998244353
const long long inf = 1e18;
const int N = 1e3 + 23;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int modplus(int x) {if (x >= mod) {x -= mod;} else if (x < 0) {x += mod;}return x;} 
int nc2(int x){x = x * (x+1);return x;}
vector<pair<int, int>> s;
vector<int> h;
vector<int> ps;
int ans = 0;
int res = 0;
void sl(int i)
{
    while (s.back().first >= h[i]) 
    {
        int x = (s.back().second - s[s.size() - 2ll].second) % mod;
        res = modplus(res - x * (nc2(s.back().first) / 2 % mod) % mod);
        s.pop_back();
    }
}
int32_t main() 
{
    int n;
    cin >> n;

    h.pb(0);
    ps.pb(0);
    for (int i = 1; i <= n; i++) 
    {
        int x;
        cin >> x;
        h.pb(x);
    }
    for (int i = 1; i <= n; i++) 
    {
        int x;
        cin >> x;
        ps.pb(x + ps[i-1]);
    }
    s.pb(make_pair(0ll,0ll));
    for (int i = 1; i <= n; i++) 
    {
        sl(i);
        if (s.back().second != ps[i-1]) 
        {
            int x = (ps[i - 1] - s.back().second) % mod;
            res = modplus(res + x * (nc2(h[i]) / 2 % mod) % mod);
            s.pb(make_pair(h[i], ps[i - 1]));
        }
        int x = (ps[i] - ps[i - 1]) % mod;
        ans = modplus(ans + res % mod * x % mod);
        ans = modplus(ans + (nc2(x) % nc2(mod)/2 % mod) * (nc2(h[i]) % nc2(mod)/2 % mod) % mod);
        res = modplus(res + (nc2(h[i]) / 2 % mod) * x % mod);
        s.pb(make_pair(h[i], ps[i]));
    }
    cout << ans;
}

• 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