oj.uz

Submission #792588

# Submission time Handle Problem Language Result Execution time Memory
792588 2023-07-25T07:12:24 Z 이성호(#10053) Real Mountains (CCO23_day1problem2) C++17
9 / 25
 63 ms 4156 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;
}
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

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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 4 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 3 ms 852 KB Output is correct
17 Correct 2 ms 788 KB Output is correct
18 Correct 2 ms 796 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 864 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 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 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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 4 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 3 ms 852 KB Output is correct
17 Correct 2 ms 788 KB Output is correct
18 Correct 2 ms 796 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 864 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 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 1 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 800 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 800 KB Output is correct
39 Correct 4 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 840 KB Output is correct
43 Correct 6 ms 852 KB Output is correct
44 Correct 6 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 852 KB Output is correct
48 Correct 4 ms 852 KB Output is correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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 4 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 3 ms 852 KB Output is correct
17 Correct 2 ms 788 KB Output is correct
18 Correct 2 ms 796 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 864 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 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 1 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 800 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 800 KB Output is correct
39 Correct 4 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 840 KB Output is correct
43 Correct 6 ms 852 KB Output is correct
44 Correct 6 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 852 KB Output is correct
48 Correct 4 ms 852 KB Output is correct
49 Incorrect 5 ms 852 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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 4 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 3 ms 852 KB Output is correct
17 Correct 2 ms 788 KB Output is correct
18 Correct 2 ms 796 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 864 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 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 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Incorrect 63 ms 4156 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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 4 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 3 ms 852 KB Output is correct
17 Correct 2 ms 788 KB Output is correct
18 Correct 2 ms 796 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 864 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 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 1 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 800 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 800 KB Output is correct
39 Correct 4 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 840 KB Output is correct
43 Correct 6 ms 852 KB Output is correct
44 Correct 6 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 852 KB Output is correct
48 Correct 4 ms 852 KB Output is correct
49 Incorrect 63 ms 4156 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory 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 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 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 4 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 3 ms 852 KB Output is correct
17 Correct 2 ms 788 KB Output is correct
18 Correct 2 ms 796 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 864 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 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 1 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 800 KB Output is correct
37 Correct 4 ms 852 KB Output is correct
38 Correct 4 ms 800 KB Output is correct
39 Correct 4 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 840 KB Output is correct
43 Correct 6 ms 852 KB Output is correct
44 Correct 6 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 852 KB Output is correct
48 Correct 4 ms 852 KB Output is correct
49 Incorrect 5 ms 852 KB Output isn't correct
50 Halted 0 ms 0 KB -