Submission #532829

#	Time	Username	Problem	Language	Result	Execution time	Memory
532829		amunduzbaev	Fire (JOI20_ho_t5)	C++17	0 / 100	1098 ms	36936 KiB

ho_t5

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 2e5 + 5;
struct ST{
	int tree[N];
	
	void add(int i, int v){
		if(!i) return;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	void add(int l, int r, int v){
		add(r, v);
		add(l - 1, -v);
	}
	
	int get(int i){
		int r=0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
}tree, cnt;

int s[N], t[N], L[N], R[N];
int l[N], r[N], res[N];
vector<int> par[N], qq[N], q2[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=q;i++){
		cin>>t[i]>>L[i]>>R[i];
		qq[R[i]].push_back(i);
		qq[L[i] - 1].push_back(-i);
	}
	
	vector<int> ss;
	for(int i=n;i>0;i--){
		while(!ss.empty() && s[ss.back()] <= s[i]) ss.pop_back();
		if(!ss.empty()) r[i] = ss.back() - 1; //, par[ss.back()].push_back(i);
		else r[i] = n;
		ss.push_back(i);
	} ss.clear();
	
	for(int i=1;i<=n;i++){
		while(!ss.empty() && s[ss.back()] < s[i]) ss.pop_back();
		if(!ss.empty()) l[i] = ss.back() + 1;
		else l[i] = 1;
		ss.push_back(i);
		for(auto j : qq[i]){
			int p = *lower_bound(ss.begin(), ss.end(), i - t[abs(j)]);
			int add = s[p] * (i - max(p, (l[p] > 1 ? l[p] + t[abs(j)] : 0)) + 1);
			if(j < 0) res[-j] -= add;
			else res[j] += add;
			q2[p - 1].push_back(j);
		}
	}
	//~ cout<<res[1]<<"\n";
	for(int i=1;i<=n;i++){
		int MX = r[i] - (l[i] > 1 ? l[i] : -N + r[i]);
		tree.add(1, r[i] - i - 1, i * s[i]);
		cnt.add(1, r[i] - i - 1, s[i]);
		tree.add(r[i] - i, MX, r[i] * s[i]);
		if(l[i] > 1){
			tree.add(1, i - l[i], -i * s[i]);
			tree.add(i - l[i] + 1, MX, -l[i] * s[i]);
			cnt.add(i - l[i] + 1, MX, -s[i]);
		} else {
			tree.add(1, MX, -i * s[i]);
		} tree.add(1, MX, s[i]);
		
		for(auto j : q2[i]){
			if(j > 0){
				res[j] += (tree.get(t[j]) + cnt.get(t[j]) * t[j]);
			}
			else {
				j = -j, res[j] -= (tree.get(t[j]) + cnt.get(t[j]) * t[j]);
			}
		}
	}
	
	for(int i=1;i<=q;i++) cout<<res[i]<<"\n";
}

/*

10 1
3 1 4 1 5 9 2 6 5 3
4 2 7

*/

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