oj.uz

답안 #968468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -