Submission #384388

#	Time	Username	Problem	Language	Result	Execution time	Memory
384388		apostoldaniel854	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	496 ms	85856 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

struct segment_tree {
    vector <pair <int, int>> seg;
    int n;
    void init (int n) {
        seg.resize (1 + 4 * n);
    }
    void build (int node, int lb, int rb, vector <int> &v) {
        if (lb == rb) {
            seg[node] = {v[lb], lb};
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        build (left_node, lb, mid, v);
        build (right_node, mid + 1, rb, v);
        seg[node] = max (seg[left_node], seg[right_node]);
    }
    pair <int, int> query_max (int node, int lb, int rb, int ql, int qr) {
        if (ql <= lb && rb <= qr)
            return seg[node];
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        pair <int, int> ans = {0, 0};
        if (ql <= mid)
            ans = max (ans, query_max (left_node, lb, mid, ql, qr));
        if (qr > mid)
            ans = max (ans, query_max (right_node, mid + 1, rb, ql, qr));
        return ans;
    }
};
const ll INF = 1e18;
struct special_set {
    multiset <pair <int, ll>> stars;
    ll more = 0;
    void update (ll x) {
        more += x;
    }
    void add (pair <int, ll> x) {
        x.second -= more;
        auto it = stars.upper_bound (x);
        if (it == stars.begin ())
            stars.insert (x);
        else {
            it = prev (it);
            if (x.second < it->second)
                stars.insert (x);
        }
        it = stars.upper_bound (x);
        while (it != stars.end () && x.second <= it->second) {
            stars.erase (it);
            it = stars.upper_bound (x);
        }
    }
    ll query (int x) {
        auto it = prev (stars.lower_bound ({x + 1, -INF}));
        return it->second + more;
    }
    int size () {
        return (int) stars.size ();
    }
    void join (special_set other) {
        for (auto it : other.stars)
            add ({it.first, it.second + other.more});
    }


};
segment_tree buildings;
const int MAX_N = 2e5;
int n;
vector <pair <int, int>> events[1 + MAX_N];
void solve (int lb, int rb, special_set &sol) {
    if (lb > rb) return;
    if (lb == rb) {
        ll total = 0;
        for (auto event : events[lb])
            total += event.second;
        sol.add ({0, total});
        for (auto event : events[lb])
            sol.add ({event.first, total - event.second});
        return;
    }
    pair <int, int> ans = buildings.query_max (1, 1, n, lb, rb);
    int mid = ans.second;
    int pivot = ans.first;
    special_set L, R;
    if (mid == rb)
        mid--;
    solve (lb, mid, L);
    solve (mid + 1, rb, R);
    ll topL = R.query (pivot), topR = L.query (pivot);
    L.update (topL);
    R.update (topR);
    if (L.size () < R.size ())
        swap (L, R);
    L.join (R);
    swap (sol, L);
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> n;
    vector <int> v (n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    buildings.init (n);
    buildings.build (1, 1, n, v);
    int m;
    cin >> m;
    while (m--) {
        int x, y, c;
        cin >> x >> y >> c;
        events[x].push_back ({y, c});
    }
    special_set sol;
    solve (1, n, sol);
    cout << sol.query (n) << "\n";
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65