Submission #1179455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179455		ian0704	Fire (JOI20_ho_t5)	C++20	100 / 100	470 ms	54204 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct SegmentTree {
    int n;
    vector<ll> tree;
    SegmentTree(int _n) : n(_n), tree(4*_n) {}

    void build(const vector<ll>& A, int node, int l, int r) {
        if (l == r) {
            tree[node] = A[l];
            return;
        }
        int m = (l + r) / 2;
        build(A, 2*node, l, m);
        build(A, 2*node+1, m+1, r);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void update(int node, int l, int r, int idx, ll val) {
        if (l == r) {
            tree[node] += val;
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m) update(2*node, l, m, idx, val);
        else update(2*node+1, m+1, r, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    ll query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        return query(2*node, l, m, ql, qr) + query(2*node+1, m+1, r, ql, qr);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N+1);
    for(int i=1;i<=N;i++) cin>>A[i];

    vector<int> p(N+1);
    stack<int> st;
    for(int i=1;i<=N;i++){
        while(!st.empty() && A[st.top()]<=A[i]) st.pop();
        p[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }

    struct Event{int t, pos; ll delta;};
    vector<Event> events;
    events.reserve(N);
    for(int i=1;i<=N;i++){
        ll last = A[i];
        int j = p[i];
        while(j>0){
            events.push_back({i-j, i, A[j]-last});
            last = A[j];
            j = p[j];
        }
    }
    sort(events.begin(), events.end(), [](auto &a, auto &b){return a.t < b.t;});

    struct Query{int T,L,R,idx;};
    vector<Query> qs(Q);
    for(int i=0;i<Q;i++){
        cin>>qs[i].T>>qs[i].L>>qs[i].R;
        qs[i].idx = i;
    }
    sort(qs.begin(), qs.end(), [](auto &a, auto &b){return a.T < b.T;});

    SegmentTree seg(N);
    seg.build(A, 1, 1, N);

    vector<ll> ans(Q);
    int ei = 0;
    for(auto &q: qs){
        while(ei < events.size() && events[ei].t <= q.T){
            seg.update(1, 1, N, events[ei].pos, events[ei].delta);
            ei++;
        }
        ans[q.idx] = seg.query(1, 1, N, q.L, q.R);
    }

    for(ll x: ans) cout<<x<<"\n";
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80