oj.uz

답안 #644275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
644275 2022-09-24T10:19:20 Z Itamar Fancy Fence (CEOI20_fancyfence) C++14
100 / 100
 26 ms 6628 KB 
// CEOI.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;
#define ll long long
#include <vector>
#define vll vector<ll>
const int m = 1e9 + 7;
ll c(ll x) {
    return ((x * (x - 1)) / 2) % m;
}

int main()
{
    int n;
    cin >> n;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vll resh(n + 2);
    vll h(n+2);
    for (int i = 0; i < n; i++) {
        int hi;
        cin >> hi;
        h[i + 1] = hi;
    }
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        resh[i + 1] = (resh[i] + w)%m;
    }
    vll v;
    vll l(n+2);
    vll r(n+2);
    for (int i = 0; i < n+2; i++) {
        while (!v.empty() && h[v.back()] > h[i]) {
            r[v.back()] = i;
            v.pop_back();
        }
        v.push_back(i);
    }
    for (int i = n+1; i >=0; i--) {
        while (!v.empty() && h[v.back()] >= h[i]) {
            l[v.back()] = i;
            v.pop_back();
        }
        v.push_back(i);
    }
    ll ans=0;
    for (int i = 1; i <= n; i++) {
        ll x = c(h[i] + 1);
        ll y = ((resh[i] - resh[l[i]]) * (resh[r[i] - 1] - resh[i - 1])) % m;
        ans = (ans + (x*y))%m;
        ans = (ans - c(resh[i] - resh[i - 1] ) * x) % m;
    }
    if (ans < 0)
        ans += m;
    cout << ans;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 9 ms 2260 KB Output is correct
4 Correct 17 ms 4588 KB Output is correct
5 Correct 17 ms 4056 KB Output is correct
6 Correct 16 ms 3576 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 932 KB Output is correct
3 Correct 15 ms 3416 KB Output is correct
4 Correct 24 ms 6496 KB Output is correct
5 Correct 25 ms 6608 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 948 KB Output is correct
4 Correct 11 ms 3416 KB Output is correct
5 Correct 23 ms 6492 KB Output is correct
6 Correct 25 ms 6624 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 12 ms 3528 KB Output is correct
10 Correct 22 ms 6348 KB Output is correct
11 Correct 24 ms 6484 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #6
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #7
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 300 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 9 ms 2776 KB Output is correct
12 Correct 19 ms 5688 KB Output is correct
13 Correct 19 ms 5212 KB Output is correct
14 Correct 17 ms 4740 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 3 ms 936 KB Output is correct
17 Correct 11 ms 3408 KB Output is correct
18 Correct 23 ms 6492 KB Output is correct
19 Correct 26 ms 6628 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 3 ms 928 KB Output is correct
22 Correct 12 ms 3524 KB Output is correct
23 Correct 21 ms 6356 KB Output is correct
24 Correct 22 ms 6448 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 308 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 316 KB Output is correct
29 Correct 1 ms 312 KB Output is correct
30 Correct 3 ms 724 KB Output is correct
31 Correct 3 ms 724 KB Output is correct
32 Correct 11 ms 2772 KB Output is correct
33 Correct 12 ms 2780 KB Output is correct
34 Correct 23 ms 5232 KB Output is correct
35 Correct 23 ms 5220 KB Output is correct
36 Correct 25 ms 5344 KB Output is correct
37 Correct 24 ms 5380 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 23 ms 5324 KB Output is correct
40 Correct 22 ms 5328 KB Output is correct
41 Correct 21 ms 5588 KB Output is correct
42 Correct 23 ms 6032 KB Output is correct