Submission #968201

# Submission time Handle Problem Language Result Execution time Memory
968201 2024-04-23T08:27:49 Z leolin0214 Real Mountains (CCO23_day1problem2) C++17
0 / 25
1 ms 600 KB
#include <iostream>
#include <vector>
#include <algorithm>
#define ff first
#define ss second
#define ll long long
using namespace std;
ll n;



template <
    class NodeType, NodeType (*combine)(NodeType, NodeType), NodeType (*unit)(),
    class TagType, NodeType (*mapping)(NodeType, TagType), TagType (*compose)(TagType, TagType)
>
struct LazySegmentTree {
    #define m ((l+r)>>1)
    #define lc (rt<<1)
    #define rc (rt<<1|1)
   
    vector<NodeType> arr;
    vector<NodeType> st;
    vector<TagType> lz;
    ll n;

    void build(ll _n) {
        build(_n, vector<NodeType>(_n+1, unit()));
    }
    template <class ArrType>
    void build(ll _n, const ArrType &_arr) {
        n = _n;
        arr.resize(n+1);
        st.resize(n*4+4);
        lz.resize(n*4+4);
        for (ll i=1; i<=n; i++) arr[i] = _arr[i];
        _build(1, n, 1);
    }

    void _build(ll l, ll r, ll rt) {
        if (l == r) {
            st[rt] = arr[l];
            return;
        }
        _build(l, m, lc);
        _build(m + 1, r, rc);
        st[rt] = combine(st[lc], st[rc]);
    }

    void push(ll rt) {
        st[lc] = mapping(st[lc], lz[rt]);
        lz[lc] = compose(lz[lc], lz[rt]);
        st[rc] = mapping(st[rc], lz[rt]);
        lz[rc] = compose(lz[rc], lz[rt]);
        lz[rt] = {0, -1};
    }

    void modify(ll ql, ll qr, TagType qx) {
        _modify(ql, qr, qx, 1, n, 1);
    }
    void _modify(ll ql, ll qr, TagType qx, ll l, ll r, ll rt) {
        if (ql <= l && r <= qr) {
            st[rt] = mapping(st[rt], qx);
            lz[rt] = compose(lz[rt], qx);
            // cout << l << "--" << r << ":" << qx.add << " " << qx.set << "\n";
            return;
        }
        if (qr < l || r < ql) return;
        push(rt);
        _modify(ql, qr, qx, l, m, lc);
        _modify(ql, qr, qx, m + 1, r, rc);
        st[rt] = combine(st[lc], st[rc]);
    }

    NodeType query(ll ql, ll qr) {
        return _query(ql, qr, 1, n, 1);
    }
    NodeType _query(ll ql, ll qr, ll l, ll r, ll rt) {
        if (qr < l || r < ql) return unit();
        if (ql <= l && r <= qr) return st[rt];
        NodeType ans = unit();
        push(rt);
        if (ql <= m) ans = combine(ans, _query(ql, qr, l, m, lc));
        if (qr > m) ans = combine(ans, _query(ql, qr, m + 1, r, rc));
        return ans;
    }

    #undef m
    #undef lc
    #undef rc
};

struct node {long long val = 0, sz = 1;};
constexpr inline node combine(node a, node b) {return {a.val+b.val, a.sz+b.sz};}
constexpr inline node unit() {return {0, 0};}
struct tag {long long add = 0, set = -1;};
constexpr node mapping(node a, tag t) {
    a.sz += t.add;
    if (t.set != -1) a.val = a.sz * t.set;
    return a;
}
constexpr tag compose(tag a, tag b) {
    a.add += b.add;
    if (b.set != -1) return {a.add, b.set};
    return a;
}
LazySegmentTree<node, combine, unit, tag, mapping, compose> ST;


long long solve1(vector<ll> h, ll n) {
    vector<pair<ll, ll>> hh(n);
    for (ll i=0; i<n; i++) hh[i] = {h[i], i};
    vector<ll> a(n);
    ll mx = 0;
    for (ll i=0; i<n; i++) {
        mx = max(mx, h[i]);
        a[i] = mx;
    }
    ll mx2 = 0;
    for (ll i=n-1; i>0; i--) {
        mx2 = max(mx2, h[i]);
        if (mx2 == mx) break;
        a[i] = mx2;
    }


    sort(hh.begin(), hh.end());
    long long ans = 0;

    LazySegmentTree<node, combine, unit, tag, mapping, compose> ST;
    ST.build(n);
    ll r = n;
    long long lh = 0;
    for (auto [x, j]:hh) {
        j++;
        while (ST.query(r, r).val >= a[r-1]) {
            ans -= lh * (lh - a[r-1]);
            r--;
        }
        
        node tmp = ST.query(j, r);
        ans += x * (tmp.sz * x - tmp.val);

        // cout << j << "-" << r << ":" << tmp.sz << " " << tmp.val << " ans: " << ans << "\n";

        ST.modify(j, j, {1, -1});
        ST.modify(j, r, {0, x});
        // cout << j << ":" << ans << "\n";
        lh = x;
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    vector<ll> h(n);
    for (ll i=0; i<n; i++) cin >> h[i];

    
    
    vector<ll> a(n);
    ll mx = 0;
    for (ll i=0; i<n; i++) {
        mx = max(mx, h[i]);
        a[i] = mx;
    }
    ll mx2 = 0;
    for (ll i=n-1; i>0; i--) {
        mx2 = max(mx2, h[i]);
        if (mx2 == mx) break;
        a[i] = mx2;
    }


    long long ans = 0;
    ans += solve1(h, n);
    reverse(h.begin(), h.end());
    // cout << "------\n";
    ans += solve1(h, n);
    reverse(h.begin(), h.end());
    for (ll i=0; i<n; i++) {
        ans += (h[i] + a[i] - 1) * (a[i] - h[i]) / 2;
        // cout << ans << "\n";
    }

    cout << ans << "\n";
}
/*
8
3 2 4 5 4 1 2 1

12
5 4 4 4 3 3 3 4 4 4 5 5
*/
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -