oj.uz

Submission #968468

# Submission time Handle Problem Language Result Execution time Memory
968468 2024-04-23T12:47:28 Z weakweakweak Real Mountains (CCO23_day1problem2) C++17
3 / 25
 14 ms 27472 KB 
//我好笨，聽解了
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int M = 1e6 + 3, N = M + 20, INF = N * 10;
 
int o[N], n;
vector <int> v[N];
 
struct segmenttree {
    int a[N << 2];
    void build (int l, int r, int id) {
        if (l == r) {
            a[id] = o[l];
            return;
        }
        int mid = (l + r) >> 1;
        build (l, mid, id << 1); build (mid + 1, r, id << 1 | 1);
        a[id] = min(a[id << 1], a[id << 1 | 1]);
    }
    int query (int l, int r, int ql, int qr, int id) {
        if (ql < 1 or qr > n or ql > qr) return INF;
        if (ql <= l and r <= qr) return a[id];
        int mid = (l + r) >> 1, ans = INT_MAX;
        if (ql <= mid) ans = min(ans, query(l, mid, ql, qr, id << 1));
        if (qr > mid)  ans = min(ans, query(mid + 1, r, ql, qr, id << 1 | 1));
        return ans;
    }
    void update (int l, int r, int pos, int val, int id) {
        if (l == r) {
            a[id] = o[pos] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(l, mid, pos, val, id << 1);
        else update(mid + 1, r, pos, val, id << 1 | 1);
        a[id] = min(a[id << 1], a[id << 1 | 1]);
    }
}seg;
 
 
int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> o[i];
        v[o[i]].push_back(i);
    }
 
    seg.build(1, n, 1);
 
    set<int> st;
    ll ans = 0;
    for (int h = 1; h <= 1000000; h++) {
        for (int x : v[h]) {
            st.insert(x);
            seg.update(1, n, x, INF, 1);
        }
        while (st.size()) {
            int i = *st.begin();
            int left = seg.query(1, n, 1, i - 1, 1),   right = seg.query(1, n, i + 1, n, 1);
            if (left == INF or right == INF) st.erase(i);
            else break;
        }
        while (st.size()) {
            int i = *st.rbegin();
            int left = seg.query(1, n, 1, i - 1, 1),   right = seg.query(1, n, i + 1, n, 1);
            if (left == INF or right == INF) st.erase(i);
            else break;
        }
        if (st.size() == 1) {
            int i = *st.begin();
            int left = seg.query(1, n, 1, i - 1, 1),   right = seg.query(1, n, i + 1, n, 1);
            ans += (left + h + right) % M;
        }
        else if (st.size() >= 2) {
            int il = *st.begin(), ir = *st.rbegin();
            ll left = seg.query(1, n, 1, il - 1, 1),   right = seg.query(1, n, ir + 1, n, 1);
            ll mid = seg.query(1, n, il + 1, ir - 1, 1);
            ans += min( (left + right + h  +  min(left, right) + (h + 1) + h)  %  M,
                        ((mid + h) * 2 + (left + right)) % M );
            ans += (st.size() - 2)  *  (h + (h + 1LL) + (h + 1) % M)  %  M;
        }
        ans %= M;
    }
 
    cout << ans << '\n';
return 0;}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct
13 Correct 13 ms 27224 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct
13 Correct 13 ms 27224 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct
13 Correct 13 ms 27224 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct
13 Correct 13 ms 27224 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct
13 Correct 13 ms 27224 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24920 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 9 ms 24924 KB Output is correct
4 Correct 12 ms 27400 KB Output is correct
5 Correct 12 ms 27228 KB Output is correct
6 Correct 11 ms 27224 KB Output is correct
7 Correct 12 ms 27228 KB Output is correct
8 Correct 11 ms 27472 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27224 KB Output is correct
11 Correct 14 ms 27224 KB Output is correct
12 Correct 11 ms 27224 KB Output is correct
13 Correct 13 ms 27224 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -