Submission #865913

#	Time	Username	Problem	Language	Result	Execution time	Memory
865913		prairie2022	Fire (JOI20_ho_t5)	C++17	0 / 100	621 ms	203968 KiB

ho_t5

#include <bits/stdc++.h>
typedef long long ll;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
using namespace std;

#define lp pos<<1
#define rp (lp)^1
#define cur (*this)[pos]
#define lc (*this)[lp]
#define rc (*this)[rp]

struct node{
    int l, r, sz = 0;
    ll val = 0, tag = 0;
};

struct TREE: vector<node> {
    void init(int l, int r, int pos){
        cur = {l, r, r-l+1, 0, 0};
        if(cur.sz>1){
            int m = (l+r)>>1;
            init(l, m, lp);
            init(m+1, r, rp);
        }
    }
    inline void push(int pos){
        lc.tag += cur.tag;
        lc.val += cur.tag*lc.sz;
        rc.tag += cur.tag;
        rc.val += cur.tag*rc.sz;
        cur.tag = 0;
    }
    void update(int l, int r, int pos, ll x){
        if(l==cur.l && r==cur.r){
            cur.tag += x;
            cur.val += x*cur.sz;
            return;
        }
        push(pos);
        if(r<rc.l) update(l, r, lp, x);
        else if(l>lc.r) update(l, r, rp, x);
        else update(l, lc.r, lp, x), update(rc.l, r, rp, x);
        cur.val = lc.val + rc.val;
    }
    ll query(int l, int r, int pos){
        if(l==cur.l && r==cur.r) return cur.val;
        push(pos);
        if(r<rc.l) return query(l, r, lp);
        else if(l>lc.r) return query(l, r, rp);
        else return query(l, lc.r, lp)+query(rc.l, r, rp);
    }
} t1, t2; // vertical, diagonal

int n;
inline ll query(int l, int r, int t){
    return t1.query(l, r, 1)+t2.query(n+l-t, n+r-t, 1);
}

int main(){
    fastio
    int q;
    cin >> n >> q;
    vector<ll> s(n+1);
    for(int i=1; i<=n; i++) cin >> s[i];
    //building segment tree
    vector<int> l(n+1), r(n+1), stk;
        //nearest larger fire
    for(int i=1; i<=n; i++){
        while(!stk.empty() && s[stk.back()]<s[i]) stk.pop_back();
        l[i] = stk.empty()?-n:stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=n; i>0; i--){
        while(!stk.empty() && s[stk.back()]<=s[i]) stk.pop_back();
        r[i] = stk.empty()?n+1:stk.back();
        stk.push_back(i);
    }
    /*for(int i=1; i<=n; i++) cout << l[i] << " \n"[i==n];
    for(int i=1; i<=n; i++) cout <<r[i] << " \n"[i==n];*/
    t1.resize(n<<2), t2.resize(n<<3);
    int ed1 = n+1, ed2 = (n<<1)^1;
    t1.init(1, ed1, 1), t2.init(1, ed2, 1);
    vector<vector<tuple<int, int, ll>>> swp(n+1); //t1+x, t2-x
        //sweeping line
    for(int i=1; i<=n; i++) t1.update(i, ed1, 1, s[i]), t2.update(n+i+1, ed2, 1, -s[i]);
    auto f = [&](int L, int R, ll val){
        L++;
        int t = R-L;
        if(t<=n) swp[t].push_back({R, n+L, val});
    };
    for(int i=1; i<=n; i++){
        f(l[i], r[i], s[i]);
        f(l[i], i, -s[i]);
        f(i, r[i], -s[i]);
    }
    /*for(int i=0; i<=n; i++){
        cout << i << " : ";
        for(const auto &tup: swp[i])
            cout << '{' << get<0>(tup) << ", " << get<1>(tup) << ", " << get<2>(tup) << "} ";
        cout << '\n';
    }
    cout << "s[0] : ";
    for(int i=1; i<=n; i++) cout << query(i, i, 0) << " \n"[i==n];*/
    //processing queries
    vector<ll> ans(q);
    vector<vector<tuple<int, int, int>>> qry(n+1);
    for(int i=0; i<n; i++){
        int T, L, R;
        cin >> T >> L >> R;
        qry[T].push_back({L, R, i});
    }
    for(int i=0; i<=n; i++){
        for(const auto &tup: swp[i]){
            t1.update(get<0>(tup), ed1, 1, get<2>(tup));
            t2.update(get<1>(tup), ed2, 1, -get<2>(tup));
        }
        for(const auto &tup: qry[i]){
            ans[get<2>(tup)] = t1.query(get<0>(tup), get<1>(tup), 1)+t2.query(n+get<0>(tup)-i, n+get<1>(tup)-i, 1);
        }
    }
    for(int i=0; i<q; i++) cout << ans[i] << '\n';
    return 0;
}

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