Submission #532826

#	Time	Username	Problem	Language	Result	Execution time	Memory
532826		amunduzbaev	Fire (JOI20_ho_t5)	C++17	100 / 100	577 ms	51204 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 << 2];
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x<<1), add(l, r, v, m+1, rx, x<<1|1);
	}
	
	int get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x];
		int m = (lx + rx) >> 1;
		if(i <= m) return get(i, lx, m, x<<1) + tree[x];
		else return get(i, m+1, rx, x<<1|1) + tree[x];
	}
}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(0, r[i] - i - 1, i * s[i]);
		cnt.add(0, r[i] - i - 1, s[i]);
		tree.add(r[i] - i, MX, r[i] * s[i]);
		if(l[i] > 1){
			tree.add(0, 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(0, MX, -i * s[i]);
		} tree.add(0, 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: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80