oj.uz

Submission #1097885

# Submission time Handle Problem Language Result Execution time Memory
1097885 2024-10-08T14:10:03 Z _8_8_ Constellation 3 (JOI20_constellation3) C++17
0 / 100
 5 ms 9820 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 2e5 + 12, MOD = (int)1e9 + 7;
const ll inf = 1e9;

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);
                upd(l, r, c - v);
            } else {
                ans += c;
            }
        }
    }
    
    cout << ans << '\n';
}

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

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

    while(t--) 
        test();

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Incorrect 4 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Incorrect 4 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Incorrect 4 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -