Submission #1097886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097886		_8_8_	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	307 ms	37460 KiB

constellation3

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 2e5 + 12, MOD = (int)1e9 + 7;


#define int ll
int n, m, a[N], it[N];
pair<ll, ll> g[N];  

vector<pair<int, int>> t[N];
vector<int> p[N];


ll f[N * 4], add[N * 4];

void inc(int v, int val) {
    f[v] += val;
    add[v] += val;
}
void push(int v) {
    if(add[v]) {
        inc(v + v, add[v]);
        inc(v + v + 1, add[v]);
        add[v] = 0;
    }
}
void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        inc(v, val);
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l, r, val, v + v, tl, tm);
        upd(l, r, val, v + v + 1, tm + 1, tr);
    }
}
ll get(int pos, int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        return f[v]; 
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        if(pos <= tm) return get(pos, v + v, tl, tm);
        return get(pos, v + v + 1, tm + 1, tr);
    }
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = n - a[i];
        p[a[i]].push_back(i);
    }
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        y = n - y + 1;
        t[y].push_back({x, c});
    }
    ll ans = 0;
    set<pair<int, int>> st;
    auto ins = [&](int i){
        auto it = st.lower_bound({i, 0});
        int l = i, r = i;
        if(it != st.end() && (*it).first == i + 1) {
            r = (*it).second;
            st.erase(it);
        }
        auto j = st.lower_bound({i, 0});
        if(j != st.begin()) {
            j--;
            if((*j).second == i - 1) {
                l = (*j).first;
                st.erase(j);
            }
        }
        st.insert({l, r});
    };
    for(int i = n; i >= 1; i--) {
        for(int j:p[i]) {
            ins(j);
        }
        for(auto [x, c]:t[i]) {
            ll v = get(x);
            if(v < c) {
                ans += v;
                auto it = st.upper_bound({x, 1e9});
                it--;
                auto [l, r] = (*it);
                assert(l <= x && x <= r);
                upd(l, r, c - v);
            } else {
                ans += c;
            }
        }
    }
    
    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 

    int t = 1; 
    // cin >> t;

    while(t--) 
        test();

    return 0;
}

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