Submission #754945

#	Time	Username	Problem	Language	Result	Execution time	Memory
754945		pcc	Fire (JOI20_ho_t5)	C++14	100 / 100	659 ms	103684 KiB

ho_t5

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

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define int ll

const ll mxn = 4e5+10;

struct Seg{
	pll segtree[mxn*4];
	Seg(){
		for(auto &i:segtree)i = {0,0};
	}
	void modify(int now,int l,int r,int s,int e,ll v){
		if(l>=s&&e>=r){
			segtree[now].sc += v;
			return;
		}
		int mid = (l+r)>>1;
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
		segtree[now].fs = 
			segtree[now*2+1].fs+segtree[now*2+1].sc*(mid-l+1)+segtree[now*2+2].fs+segtree[now*2+2].sc*(r-mid);
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r){
			return segtree[now].fs+segtree[now].sc*(r-l+1);
		}
		int mid = (l+r)>>1;
		if(mid>=e)return getval(now*2+1,l,mid,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1);
		else if(mid<s)return getval(now*2+2,mid+1,r,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1);
		else return getval(now*2+1,l,mid,s,e)+getval(now*2+2,mid+1,r,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1);
	}
};
Seg seg1,seg2;
vector<pll> op[mxn];
ll arr[mxn];
ll n,q;
vector<tuple<ll,ll,ll>> req[mxn];
pll range[mxn];
ll ans[mxn];
ll sh = mxn>>1;

void addtri(int r,int c,ll val){
	op[c].push_back({r,val});
}

void add(int now,int h,int w){
	//cout<<now<<":"<<h<<' '<<w<<endl;
	addtri(now,0,arr[now]);
	addtri(now,h,-arr[now]);
	addtri(now+w,w,-arr[now]);
	addtri(now+w,h+w,arr[now]);
	return;
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i = 1;i<=q;i++){
		ll t,l,r;
		cin>>t>>l>>r;
		req[t].push_back(make_tuple(1LL*i,l,r));
	}
	arr[0] = arr[n+1] = 1e18;
	deque<int> dq;
	dq.push_back(0);
	for(int i = 1;i<=n;i++){
		while(arr[dq.back()]<=arr[i])dq.pop_back();
		range[i].fs = dq.back();
		dq.push_back(i);
	}
	dq.clear();
	dq.push_back(n+1);
	for(int i = n;i>=1;i--){
		while(arr[dq.back()]<arr[i])dq.pop_back();
		range[i].sc = dq.back();
		dq.push_back(i);
		//cout<<i<<":"<<range[i].fs<<' '<<range[i].sc<<'\n';
	}
	for(int i = 1;i<=n;i++){
		if(range[i].fs == 0)range[i].fs = n+1;
		else range[i].fs = i-range[i].fs;
		range[i].sc = range[i].sc-i;
		add(i,range[i].fs,range[i].sc);
	}
	for(int i = 0;i<=n;i++){
		for(auto &j:op[i]){
			seg1.modify(0,1,mxn,j.fs,mxn,j.sc);
			seg2.modify(0,1,mxn,sh+j.fs+1,mxn,-j.sc);
		}
		for(auto &j:req[i]){
			ans[get<0>(j)] = 
				seg1.getval(0,1,mxn,get<1>(j),get<2>(j))+seg2.getval(0,1,mxn,sh+get<1>(j),sh+get<2>(j));
		}
		/*
		for(int i = 1;i<=n;i++)cout<<seg1.getval(0,1,mxn,i,i)<<' ';cout<<endl;
		for(int i  = 1;i<=n;i++)cout<<seg2.getval(0,1,mxn,sh+i,sh+i)<<' ';cout<<endl;

	   */
		sh--;
	}
	for(int i = 1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}

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