oj.uz

Submission #968465

# Submission time Handle Problem Language Result Execution time Memory
968465 2024-04-23T12:46:44 Z weakweakweak Real Mountains (CCO23_day1problem2) C++17
3 / 25
 13 ms 27736 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 + 1) + (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 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct
13 Correct 12 ms 27480 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 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct
13 Correct 12 ms 27480 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 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct
13 Correct 12 ms 27480 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 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct
13 Correct 12 ms 27480 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 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct
13 Correct 12 ms 27480 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 11 ms 24924 KB Output is correct
2 Correct 10 ms 24924 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 13 ms 27736 KB Output is correct
5 Correct 12 ms 27484 KB Output is correct
6 Correct 11 ms 27484 KB Output is correct
7 Correct 11 ms 27484 KB Output is correct
8 Correct 11 ms 27484 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 12 ms 27224 KB Output is correct
11 Correct 13 ms 27484 KB Output is correct
12 Correct 11 ms 27328 KB Output is correct
13 Correct 12 ms 27480 KB Output is correct
14 Incorrect 9 ms 24924 KB Output isn't correct
15 Halted 0 ms 0 KB -