oj.uz

Submission #895162

# Submission time Handle Problem Language Result Execution time Memory
895162 2023-12-29T13:56:03 Z sleepntsheep Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 468 KB 
#include <iostream>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

int main()
{
    constexpr i64 mod { 1000000007 };
    ShinLena;
    int n;
    cin >> n;
    vector<int> h(n+1), w(n+1), l(n+1), r(n+1), p(n+1);
    vector<i64> ww(n+1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> w[i], ww[i] = ww[i-1] + w[i];
    for (int i = 1; i <= n; ++i)
    {
        p[i] = i - 1;
        while (h[p[i]] > h[i])
            p[i] = p[p[i]];
        l[i] = r[p[i]];
        r[p[i]] = i;
        p[l[i]] = i;
    }

    i64 ans = 0;
    auto dfs = [&](auto &&dfs, int u, int ll, int rr)
    {
        if (!u) return;
        if (ll > rr) return;

        i64 w1 = ww[rr] - ww[ll-1];

        auto C2 = [](i64 x) { return x * (x+1) % mod * 500000004ll % mod; };
        (ans += C2(w1) * h[u] % mod) %= mod;

        dfs(dfs, l[u], ll, u-1);
        dfs(dfs, r[u], u+1, rr);
    };

    for (int i = 1; i <= n; ++i) if (!p[i]) dfs(dfs, i, 1, n);

    cout << ans << '\n';

    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -