Submission #534888

#	Time	Username	Problem	Language	Result	Execution time	Memory
534888		mjhmjh1104	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	52 ms	7148 KiB

fancyfence

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

int n, h[100006], w[100006], res, sum[100006];
vector<int> v;

int get(int x, int y) {
    return (sum[y] - (x ? sum[x - 1] : 0) + MOD) % MOD;
}

pair<int, int> tree[262144];

pair<int, int> query(int i, int b, int e, int l, int r) {
    if (r < l || r < b || e < l) return { (int)2e9, -1 };
    if (l <= b && e <= r) return tree[i];
    int m = (b + e) / 2;
    return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}

void dnc(int l, int r, int curr) {
    if (l > r) return;
    int m = query(0, 0, 131071, l, r).second;
    int c = get(l, r);
    int x = (1LL * h[m] * (h[m] + 1) / 2 % MOD - 1LL * curr * (curr + 1) / 2 % MOD + MOD) % MOD;
    res = (res + 1LL * x * (1LL * c * (c + 1) / 2 % MOD) % MOD) % MOD;
    dnc(l, m - 1, h[m]);
    dnc(m + 1, r, h[m]);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", h + i);
    for (int i = 0; i < n; i++) scanf("%d", w + i);
    sum[0] = w[0];
    for (int i = 1; i < n; i++) sum[i] = (sum[i - 1] + w[i]) % MOD;
    for (int i = 0; i < n; i++) tree[131071 + i] = { h[i], i };
    for (int i = 131070; i >= 0; i--) tree[i] = min(tree[i * 2 + 1], tree[i * 2 + 2]);
    dnc(0, n - 1, 0);
    printf("%d", res);
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fancyfence.cpp:36:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     for (int i = 0; i < n; i++) scanf("%d", h + i);
      |                                 ~~~~~^~~~~~~~~~~~~
fancyfence.cpp:37:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     for (int i = 0; i < n; i++) scanf("%d", w + i);
      |                                 ~~~~~^~~~~~~~~~~~~

• 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