Submission #881420

#	Time	Username	Problem	Language	Result	Execution time	Memory
881420		Danet	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	1 ms	856 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};
const int two = (mod + 1)/ 2;
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;
int res = 0;
int ans = 0;
vector<int> h;
vector<int> ps;
int tmp = 0;
void sl(int i)
{
    while (s.back().first >= h[i]) 
    {
        tmp = (s.back().second - s[s.size() - 2ll].second) % mod;
        res = modplus(res - tmp * ( nc2(s.back().first) / 2 % mod) % mod);
        s.pop_back();
    }
    if (s.back().second != ps[i-1]) 
    {
        int x = (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() 
{
    tof_io;
    int n;
    cin >> n;

    h.pb(0);
    ps.pb(0);
    for (int i = 1; i <= n; i++) 
    {
        cin >> h[i];
    }
    for (int i = 1; i <= n; i++) 
    {
        cin >> ps[i];
        ps[i] = ps[i] + ps[i - 1];
    }
    
    s.pb(make_pair(0ll,0ll));

    for (int i = 1; i <= n; i++) 
    {
        sl(i);
        int x = (ps[i] - ps[i - 1]) % mod;
        ans = modplus(ans + res % mod * x % mod);
        ans = modplus( ans + (nc2(x) % mod * two % mod) * (nc2(h[i]) * two % mod) % mod );
        res = modplus(res + (nc2(h[i]) / 2 % mod) * x % mod);
        s.pb(make_pair(h[i], ps[i]));
    }
    
    cout << ans;
}

Compilation message (stderr)

fancyfence.cpp: In function 'void sl(long long int)':
fancyfence.cpp:37:13: warning: unused variable 'x' [-Wunused-variable]
   37 |         int x = (ps[i - 1] - s.back().second) % mod;
      |             ^

• 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