Submission #235533

#	Time	Username	Problem	Language	Result	Execution time	Memory
235533		oolimry	Fire (JOI20_ho_t5)	C++14	13 / 100	297 ms	37812 KiB

ho_t5

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define all(x) x.begin(), x.end()
using namespace std;

const int N = 200005;
struct RURQ{
	long long tree1[400014];
	long long tree2[400014];
	
	inline void update(long long l, long long r, long long v){
		l += N, r += N;
		int L = l, R = r;
		for(r++;r <= 2*N;r += (r & -r)){
			tree1[r] -= v;
			tree2[r] -= R*v;
		}
		for(;l <= 2*N;l += (l & -l)){
			tree1[l] += v;
			tree2[l] += (L-1)*v;
		}
	}
	
	inline long long query(long long r){
		long long R = r;
		long long ans = 0;
		for(;r;r -= (r & -r)){
			ans += R * tree1[r];
			ans -= tree2[r];
		}
		return ans;
	}
	
	inline long long query(int l, int r){
		l += N, r += N;
		return query(r) - query(l-1);
	}
} vert, diag;

struct QU{ int l, r; long long v; }; //Query or Update

vector<QU> queries[200005];
vector<QU> updates[200005];
int arr[200005];
int ans[200005];
int L[200005];
int R[200005];

void tri(int l, int r, long long v){
	if(r < l) return;
	diag.update(l, N, v);
	vert.update(r+1, N, -v);
	
	if(r-l+1 < N) updates[r-l+1].push_back({l, r, v});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	
	for(int i = 1;i <= n;i++) cin >> arr[i];
	
	for(int i = 1;i <= Q;i++){
		int t, l, r; cin >> t >> l >> r;
		queries[t].push_back({l,r,i});
	}
	
	stack<int> S;
	for(int i = 1;i <= n;i++){
		while(!S.empty() && arr[S.top()] < arr[i]) S.pop();
		if(S.empty()) L[i] = -N+1;
		else L[i] = S.top();
		S.push(i);
	}
	
	while(!S.empty()) S.pop();
	for(int i = n;i >= 0;i--){
		while(!S.empty() && arr[S.top()] <= arr[i]) S.pop();
		if(S.empty()) R[i] = N-1;
		else R[i] = S.top();
		S.push(i);
	}
	
	
	for(int i = 1;i <= n;i++){
		tri(L[i]+1,R[i]-1,arr[i]);
		tri(L[i]+1,i-1,-arr[i]);
		tri(i+1,R[i]-1,-arr[i]);
	}
	
	for(int t = 1;t <= n;t++){
		for(QU u : updates[t]){
			diag.update(u.l, N, -u.v);
			vert.update(u.r+1, N, u.v);
		}
		
		for(QU q : queries[t]){
			ans[q.v] = diag.query(q.l - t, q.r - t) + vert.query(q.l, q.r);
		}
	}
	
	for(int i = 1;i <= Q;i++) cout << ans[i] << "\n";	
	
	return 0;
}

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