oj.uz

Submission #792592

# Submission time Handle Problem Language Result Execution time Memory
792592 2023-07-25T07:14:51 Z 이성호(#10053) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 3 ms 852 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) % mod) * (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
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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 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 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -