Submission #969895

#	Time	Username	Problem	Language	Result	Execution time	Memory
969895		happy_node	Fire (JOI20_ho_t5)	C++17	100 / 100	619 ms	154756 KiB

ho_t5

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

const int MX=4e5+5;
const int o=2e5;

int N,Q;
ll S[MX], T[MX], L[MX], R[MX], ans[MX];

struct segtree {
        ll t[4 * MX], lazy[4 * MX];

        void push(int v, int l, int r) {
        	if(lazy[v]==0) return;

        	t[v]+=lazy[v]*(r-l+1);
        	if(l!=r) {
        		lazy[v*2+0]+=lazy[v];
        		lazy[v*2+1]+=lazy[v];
        	}
        	lazy[v]=0;
        }
 
        void update(int v, int l, int r, int ql, int qr, int val) {
        	push(v,l,r);
                if(qr<l || r<ql) return;
                if(ql<=l&&qr>=r) {
                        lazy[v]+=val;
                        push(v,l,r);
                        return;
                }
                int mid = (l + r) >> 1;
                update(v * 2 + 0, l, mid + 0, ql, qr, val);
                update(v * 2 + 1, mid + 1, r, ql, qr, val);
                t[v] = t[v * 2 + 0] + t[v * 2 + 1];
        }
 
        ll query(int v, int l, int r, int ql, int qr) {
        	push(v,l,r);
                if(ql > r || qr < l) return 0;
                if(ql <= l && qr >= r) return t[v];
                int mid = (l + r) >> 1;
                return query(v * 2 + 0, l, mid + 0, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr);
        }

        void upd(int l, int r, int val) {
        	l+=o,r+=o;
        	update(1,0,o+o,l,r,val);
        }

        ll que(int l, int r) {
        	l+=o,r+=o;
        	return query(1,0,o+o,l,r);
        }
} st, tt;

// st -> diagonal, tt -> normal segtree

vector<array<ll,3>> del[MX];
vector<array<ll,3>> qry[MX];

vector<array<ll,3>> dg[MX], vt[MX];

void tri(int l, int r, ll val) {
	if(l>r) return;

	int t=r-l+1;
	dg[0].push_back({l,o,val});
	vt[0].push_back({r+1,o,-val});

	dg[t].push_back({l,o,-val});
	vt[t].push_back({r+1,o,val});
}

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

	cin>>N>>Q;
	for(int i=1;i<=N;i++) cin>>S[i];

	vector<int> stk;
	for(int i=N;i>=1;i--) {
		while(!stk.empty() && S[stk.back()]<=S[i]) stk.pop_back();
		if(stk.size()) {
			R[i]=stk.back();
		} else {
			R[i]=N+1;
		}
		stk.push_back(i);
	}

	stk.clear();

	for(int i=1;i<=N;i++) {
		while(!stk.empty() && S[stk.back()]<S[i]) stk.pop_back();
		if(stk.size()) {
			L[i]=stk.back();
		} else {
			L[i]=-o;
		}
		stk.push_back(i);
	}

	for(int i=1;i<=Q;i++) {
		int t,l,r;
		cin>>t>>l>>r;
		qry[t].push_back({l,r,i});
	}

	for(int i=1;i<=N;i++) {
		tri(L[i]+1,R[i]-1,S[i]);
		tri(L[i]+1,i-1,-S[i]);
		tri(i+1,R[i]-1,-S[i]);
	}

	for(int t=0;t<=N;t++) {
		for(auto [l,r,val]:dg[t]) {
			st.upd(l,r,val);
		}
		for(auto [l,r,val]:vt[t]) {
			tt.upd(l,r,val);
		}
		for(auto [l,r,id]:qry[t]) {
			ans[id]=st.que(l-t,r-t)+tt.que(l,r);
		}
	}

	for(int i=1;i<=Q;i++) {
		cout<<ans[i]<<'\n';
	}

}

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