Submission #1030061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030061		Neco_arc	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	20 ms	5980 KiB

fancyfence

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Fancy Fence"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}


int n;
ll h[maxn], w[maxn];
ll s[maxn], Sum[maxn];
int top, q[maxn];

ll md(ll x) { return ((x % mod) + mod) % mod; }
ll calc(ll x) { return md(x * (x + 1) / 2); }

void solve()
{

    cin >> n;
    fi(i, 1, n) cin >> h[i];
    fi(i, 1, n) cin >> w[i];


    fi(i, 1, n) s[i] = md(s[i - 1] + w[i]);

    ll ans = 0;
    fi(i, 1, n) {
        while(top && h[i] < h[q[top]]) --top;
        ll Len = md(s[i] - s[q[top]]);

        ans = md(ans + md(calc(w[i]) * calc(h[i])));
        ans = md( ans + md(md(md(Len - w[i]) * w[i]) * calc(h[i])) );
        ans = md(ans + md(Sum[top] * w[i]));

        q[++top] = i;
        Sum[top] = md(Sum[top - 1] + md(Len * calc(h[i])));


    }

    cout << ans;

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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