oj.uz

Submission #492486

# Submission time Handle Problem Language Result Execution time Memory
492486 2021-12-07T14:20:17 Z LittleCube Fancy Fence (CEOI20_fancyfence) C++14
100 / 100
 82 ms 5852 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll MOD = 1000000007;
const ll inv2 = 500000004;

int N;
ll h[100005], w[100005], ans;
vector<pll> mono = {pll{0, 0}};

signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> h[i];
    for (int i = 1; i <= N; i++)
        cin >> w[i];
    N++;
    for (int i = 1; i <= N; i++)
    {

        while (h[i] < mono.back().F)
        {
            if (h[i] < mono[mono.size() - 2].F)
            {
                ans = (ans + (((((mono.back().S * (mono.back().S + 1) % MOD) * inv2 % MOD) * (mono[mono.size() - 1].F - mono[mono.size() - 2].F) % MOD) * (mono[mono.size() - 1].F + mono[mono.size() - 2].F + 1) % MOD) * inv2 % MOD)) % MOD;
                mono[mono.size() - 2].S = (mono.back().S + mono[mono.size() - 2].S) % MOD;
            }
            else
            {
                ans = (ans + (((((mono.back().S * (mono.back().S + 1) % MOD) * inv2 % MOD) * (mono[mono.size() - 1].F - h[i]) % MOD) * (mono[mono.size() - 1].F + h[i] + 1) % MOD) * inv2 % MOD)) % MOD;
                w[i] = (mono.back().S + w[i]) % MOD;
            }

            mono.pop_back();
            //for (pll i : mono)
            //    cout << "(" << i.F << ", " << i.S << ") ";
            //cout << " | " << ans << '\n';
        }
        if (h[i] == mono.back().F)
            mono.back().S = (mono.back().S + w[i]) % MOD;
        else
            mono.emplace_back(pll{h[i], w[i]});

        //for (pll i : mono)
        //    cout << "(" << i.F << ", " << i.S << ") ";
        //cout << " | " << ans << '\n';
    }
    cout << ans << '\n';
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 30 ms 1636 KB Output is correct
4 Correct 54 ms 2884 KB Output is correct
5 Correct 56 ms 2980 KB Output is correct
6 Correct 51 ms 2944 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 41 ms 984 KB Output is correct
4 Correct 77 ms 1860 KB Output is correct
5 Correct 76 ms 1768 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 8 ms 420 KB Output is correct
4 Correct 36 ms 944 KB Output is correct
5 Correct 74 ms 1816 KB Output is correct
6 Correct 75 ms 1740 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 8 ms 844 KB Output is correct
9 Correct 40 ms 1700 KB Output is correct
10 Correct 80 ms 4028 KB Output is correct
11 Correct 80 ms 4032 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 0 ms 300 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 26 ms 1640 KB Output is correct
12 Correct 51 ms 2920 KB Output is correct
13 Correct 54 ms 3140 KB Output is correct
14 Correct 53 ms 2880 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 8 ms 572 KB Output is correct
17 Correct 36 ms 1968 KB Output is correct
18 Correct 74 ms 3736 KB Output is correct
19 Correct 80 ms 3884 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 8 ms 972 KB Output is correct
22 Correct 38 ms 2624 KB Output is correct
23 Correct 72 ms 5852 KB Output is correct
24 Correct 76 ms 5844 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 10 ms 564 KB Output is correct
31 Correct 8 ms 628 KB Output is correct
32 Correct 36 ms 1888 KB Output is correct
33 Correct 39 ms 1924 KB Output is correct
34 Correct 74 ms 3676 KB Output is correct
35 Correct 72 ms 3580 KB Output is correct
36 Correct 76 ms 3692 KB Output is correct
37 Correct 82 ms 3708 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 74 ms 3708 KB Output is correct
40 Correct 77 ms 3728 KB Output is correct
41 Correct 79 ms 4292 KB Output is correct
42 Correct 75 ms 4924 KB Output is correct