Submission #1065589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065589		_8_8_	Fire (JOI20_ho_t5)	C++17	100 / 100	543 ms	127012 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 4e5 + 12, MOD = (int)1e9 + 7;

int n,q,s[N];
vector<array<int,3>> qr[N];
struct segtree {
    vector<ll> t,add;
    void init() {
        t.assign(N * 4,0);
        add.assign(N * 4,0);
    }
    void inc(int v,ll val,int tl,int tr) {
        add[v] += val;
        t[v] += val*1ll* (tr - tl + 1);
    }
    void push(int v,int tl,int tr) {
        if(add[v]) {
            int tm = (tl + tr) >> 1;
            inc(v + v,add[v],tl,tm);
            inc(v + v + 1,add[v],tm+1,tr);
            add[v] = 0;
        }
    }
    void upd(int l,int r,ll 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,tl,tr); 
        } else {
            push(v,tl,tr);
            int tm = (tl + tr) >> 1;
            upd(l,r,val,v+v,tl,tm);
            upd(l,r,val,v+v+1,tm+1,tr);
            t[v] = t[v + v] + t[v + v + 1];
        }
    }
    ll get(int l,int r,int v = 1,int tl = 1,int tr = n) {
        if(l > r || tl >r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        push(v,tl,tr);
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
}t_[3];
int prv[N],nx[N];
vector<array<int,4>> sub[N];
void prec() {
    for(int i = 0;i < 3;++i) t_[i].init();
    vector<int> st;
    for(int i = 1;i <= n;i++) {
        while(!st.empty() && s[st.back()] <= s[i]) {
            st.pop_back();
        }
        if(!st.empty()) {
            prv[i] = st.back();
        } 
        st.push_back(i);
    }
    st.clear();
    for(int i = n;i >= 1;i--) {
        while(!st.empty() && s[st.back()] < s[i]) {
            st.pop_back();
        }
        if(!st.empty()) {
            nx[i] = st.back();
        } else {
            nx[i] = n + 1;
        }
        st.push_back(i);
    }
    auto triag = [&](int i,int s,int val) {
        ++s;
        int l = i,r = i + s - 1;
        if(l > r) return;
        sub[s].push_back({l,n,-val,0});
        sub[s].push_back({r+1,n,val,1});
        t_[0].upd(l,n,val);
        t_[1].upd(r + 1,n,-val);
    };
    for(int i = 1;i <= n;i++) {
        if(prv[i]) {
            triag(prv[i] + 1,nx[i] - 1 - (prv[i] + 1),s[i]);
            triag(prv[i] + 1,i - prv[i] - 2,-s[i]);
            triag(i + 1,(nx[i] - 1) - (i + 1),-s[i]);
        } else {
            int _s = nx[i] - i;
            // cout << i << ' ' << i + _s - 1 << '\n';
            t_[1].upd(i,i + _s - 1,s[i]);
            // cout << i + 1 << ' ' << _s - 1 << "\n";
            triag(i+1,_s-2,-s[i]);
        }
    }
}
ll ans[N];
void test() {
    cin >> n >> q;
    for(int i = 1;i <= n;i++) {
        cin >> s[i];   
    }
    prec();
    for(int i = 1;i <= q;i++) {
        int l,r,t;
        cin >> t >> l >> r;
        qr[t].push_back({l,r,i});
    }
    for(int t = 0;t <= n;t++) {
        for(auto [l,r,v,id]:sub[t]) {
            t_[id].upd(l,r,v);
        }
        for(auto [l,r,i]:qr[t]) {
            ans[i] = t_[0].get(l-t,r-t) + t_[1].get(l,r);
        }
    }
    for(int i = 1;i <= q;++i) {
        cout << ans[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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