Submission #881460

#	Time	Username	Problem	Language	Result	Execution time	Memory
881460		Danet	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	68 ms	6180 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;
vector<int> ks;
int ans = 0;
int res = 0;
void sl(int i){while (s.back().first >= h[i]) {int tmp = (s.back().second - s[s.size() - 2ll].second) % mod;res = modplus(res - tmp * (nc2(s.back().first) / 2 % mod) % mod);s.pop_back();}}
void cal(int i)
{
int tmp = ks[i] % mod;
ans = modplus(ans + res % mod * tmp % mod);
ans = modplus(ans + (nc2(tmp) % nc2(mod)/2 % mod) * (nc2(h[i]) % nc2(mod)/2 % mod) % mod);
res = modplus(res + (nc2(h[i]) / 2 % mod) * tmp % mod);
s.pb(make_pair(h[i], ps[i]));
}
void cand(int i)
{
    if (s.back().second != ps[i-1]) 
    {
        int tmp = (ps[i - 1] - s.back().second) % mod;
        res = modplus(res + tmp * (nc2(h[i]) / 2 % mod) % mod);
        s.pb(make_pair(h[i], ps[i - 1]));
    }
}
int32_t main() 
{
    int n;
    cin >> n;

    h.pb(0);
    ps.pb(0);
    ks.pb(0);
    for (int i = 0; i < n; i++) 
    {
        int x;
        cin >> x;
        h.pb(x);
    }
    for (int i = 0; i < n; i++) 
    {
        int x;
        cin >> x;
        ks.pb(x);
        ps.pb(x + ps[i]);
    }
    s.pb(make_pair(0ll,0ll));
    for (int i = 0; i < n; i++) 
    {
        sl(i + 1);
        cand(i + 1);
        cal(i + 1);
    }
    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