oj.uz

Submission #968476

# Submission time Handle Problem Language Result Execution time Memory
968476 2024-04-23T13:04:24 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 ,
                        (mid + h) * 2 + (left + right) ) % M;
            ans += (st.size() - 2)  *  (h + h + 1LL + h + 1)  %  M;
        }
        ans %= M;
    }
 
    cout << ans << '\n';
return 0;}

Subtask #1
3.0 / 3.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25048 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 10 ms 25088 KB Output is correct
4 Correct 14 ms 27228 KB Output is correct
5 Correct 13 ms 27228 KB Output is correct
6 Correct 12 ms 27228 KB Output is correct
7 Correct 12 ms 27472 KB Output is correct
8 Correct 11 ms 27228 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27244 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 12 ms 27228 KB Output is correct
14 Incorrect 9 ms 25092 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 25048 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 10 ms 25088 KB Output is correct
4 Correct 14 ms 27228 KB Output is correct
5 Correct 13 ms 27228 KB Output is correct
6 Correct 12 ms 27228 KB Output is correct
7 Correct 12 ms 27472 KB Output is correct
8 Correct 11 ms 27228 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27244 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 12 ms 27228 KB Output is correct
14 Incorrect 9 ms 25092 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 25048 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 10 ms 25088 KB Output is correct
4 Correct 14 ms 27228 KB Output is correct
5 Correct 13 ms 27228 KB Output is correct
6 Correct 12 ms 27228 KB Output is correct
7 Correct 12 ms 27472 KB Output is correct
8 Correct 11 ms 27228 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27244 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 12 ms 27228 KB Output is correct
14 Incorrect 9 ms 25092 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 25048 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 10 ms 25088 KB Output is correct
4 Correct 14 ms 27228 KB Output is correct
5 Correct 13 ms 27228 KB Output is correct
6 Correct 12 ms 27228 KB Output is correct
7 Correct 12 ms 27472 KB Output is correct
8 Correct 11 ms 27228 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27244 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 12 ms 27228 KB Output is correct
14 Incorrect 9 ms 25092 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 25048 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 10 ms 25088 KB Output is correct
4 Correct 14 ms 27228 KB Output is correct
5 Correct 13 ms 27228 KB Output is correct
6 Correct 12 ms 27228 KB Output is correct
7 Correct 12 ms 27472 KB Output is correct
8 Correct 11 ms 27228 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27244 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 12 ms 27228 KB Output is correct
14 Incorrect 9 ms 25092 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 25048 KB Output is correct
2 Correct 9 ms 24924 KB Output is correct
3 Correct 10 ms 25088 KB Output is correct
4 Correct 14 ms 27228 KB Output is correct
5 Correct 13 ms 27228 KB Output is correct
6 Correct 12 ms 27228 KB Output is correct
7 Correct 12 ms 27472 KB Output is correct
8 Correct 11 ms 27228 KB Output is correct
9 Correct 12 ms 27228 KB Output is correct
10 Correct 11 ms 27244 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 12 ms 27228 KB Output is correct
14 Incorrect 9 ms 25092 KB Output isn't correct
15 Halted 0 ms 0 KB -