oj.uz

답안 #792597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792597 2023-07-25T07:16:17 Z 이성호(#10053) Real Mountains (CCO23_day1problem2) C++17
12 / 25
 71 ms 4144 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define int long long
using namespace std;

const int sz = 1 << 19;
const int inf = 1e18;
const int mod = 1000003;

int N, H[500005], goal[500005], tree[1<<20];

int init(int s = 1, int e = N, int node = 1)
{
    if (s == e) return tree[node] = H[s];
    return tree[node] = min(init(s, (s+e)/2, 2*node), init((s+e)/2+1, e, 2*node+1));
}

int query(int l, int r, int s = 1, int e = N, int node = 1)
{
    if (e < l || r < s) return inf;
    if (l <= s && e <= r) return tree[node];
    return min(query(l, r, s, (s+e)/2, 2*node), query(l, r, (s+e)/2+1, e, 2*node+1));
}


int calc(int h, int k, int m1, int m2, int m)
{
    if (k == 1) return (m1 + m2) * (m - h) + (m + h - 1) * (m - h) / 2;
    else return (m1 + m2 + m + 2 * k - 3) * (m - h) + (3 * k - 3) * (((h + m - 1) * (m - h) / 2) % mod);
}
vector<int> cpx;
int nxt(int k)
{
    return *++lower_bound(cpx.begin(), cpx.end(), k);
}
signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> H[i];
    cpx.clear();
    for (int i = 1; i <= N; i++) cpx.push_back(H[i]);
    sort(cpx.begin(), cpx.end());
    cpx.erase(unique(cpx.begin(), cpx.end()), cpx.end());
    int peak = max_element(H+1, H+N+1) - H;
    for (int i = 1; i <= peak; i++) {
        goal[i] = max(goal[i-1], H[i]);
    }
    for (int i = N; i >= peak + 1; i--) {
        goal[i] = max(goal[i+1], H[i]);
    }
    int gl = 1, gr = N;
    vector<pair<int, int>> vc;
    for (int i = 1; i <= N; i++) {
        vc.push_back(make_pair(H[i], i));
    }
    sort(vc.begin(), vc.end());
    int cur = vc[0].first;
    int pv = 0;
    set<int> st;
    int ans = 0;
    init();
    while (pv < N && vc[pv].first == cur) st.insert(vc[pv++].second);
    while (1) {
        while (gl <= gr && goal[gl] == cur) gl++;
        while (gl <= gr && goal[gr] == cur) gr--;
        if (gl > gr) break;
        while (!st.empty() && *st.begin() <= gl) st.erase(st.begin());
        while (!st.empty() && *--st.end() >= gr) st.erase(--st.end());
        if (!st.empty()) {
            int m = nxt(cur);
            int m1 = query(gl, *st.begin() - 1);
            int m2 = query(*--st.end() + 1, gr);
            int k = st.size();
            ans += calc(cur, k, m1, m2, m);
            ans %= mod;
        }
        cur = nxt(cur);
        while (pv < N && vc[pv].first == cur) st.insert(vc[pv++].second);
    }
    cout << (ans % mod + mod) % mod << '\n';
    return 0;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 4 ms 852 KB Output is correct
36 Correct 4 ms 852 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 856 KB Output is correct
39 Correct 5 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 2 ms 852 KB Output is correct
42 Correct 2 ms 852 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 4 ms 852 KB Output is correct
46 Correct 4 ms 852 KB Output is correct
47 Correct 4 ms 872 KB Output is correct
48 Correct 5 ms 852 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 4 ms 852 KB Output is correct
36 Correct 4 ms 852 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 856 KB Output is correct
39 Correct 5 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 2 ms 852 KB Output is correct
42 Correct 2 ms 852 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 4 ms 852 KB Output is correct
46 Correct 4 ms 852 KB Output is correct
47 Correct 4 ms 872 KB Output is correct
48 Correct 5 ms 852 KB Output is correct
49 Correct 6 ms 852 KB Output is correct
50 Correct 4 ms 852 KB Output is correct
51 Correct 4 ms 852 KB Output is correct
52 Correct 4 ms 852 KB Output is correct
53 Correct 4 ms 852 KB Output is correct
54 Correct 2 ms 788 KB Output is correct
55 Correct 2 ms 852 KB Output is correct
56 Correct 2 ms 852 KB Output is correct
57 Correct 4 ms 792 KB Output is correct
58 Correct 4 ms 852 KB Output is correct
59 Correct 4 ms 852 KB Output is correct
60 Correct 5 ms 852 KB Output is correct
61 Correct 4 ms 852 KB Output is correct
62 Correct 5 ms 852 KB Output is correct

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Incorrect 71 ms 4144 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 4 ms 852 KB Output is correct
36 Correct 4 ms 852 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 856 KB Output is correct
39 Correct 5 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 2 ms 852 KB Output is correct
42 Correct 2 ms 852 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 4 ms 852 KB Output is correct
46 Correct 4 ms 852 KB Output is correct
47 Correct 4 ms 872 KB Output is correct
48 Correct 5 ms 852 KB Output is correct
49 Incorrect 71 ms 4144 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 2 ms 852 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 4 ms 852 KB Output is correct
36 Correct 4 ms 852 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 856 KB Output is correct
39 Correct 5 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 2 ms 852 KB Output is correct
42 Correct 2 ms 852 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 4 ms 852 KB Output is correct
46 Correct 4 ms 852 KB Output is correct
47 Correct 4 ms 872 KB Output is correct
48 Correct 5 ms 852 KB Output is correct
49 Correct 6 ms 852 KB Output is correct
50 Correct 4 ms 852 KB Output is correct
51 Correct 4 ms 852 KB Output is correct
52 Correct 4 ms 852 KB Output is correct
53 Correct 4 ms 852 KB Output is correct
54 Correct 2 ms 788 KB Output is correct
55 Correct 2 ms 852 KB Output is correct
56 Correct 2 ms 852 KB Output is correct
57 Correct 4 ms 792 KB Output is correct
58 Correct 4 ms 852 KB Output is correct
59 Correct 4 ms 852 KB Output is correct
60 Correct 5 ms 852 KB Output is correct
61 Correct 4 ms 852 KB Output is correct
62 Correct 5 ms 852 KB Output is correct
63 Incorrect 71 ms 4144 KB Output isn't correct
64 Halted 0 ms 0 KB -