Submission #1277090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277090		PieArmy	Fire (JOI20_ho_t5)	C++20	100 / 100	668 ms	76088 KiB

ho_t5

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

struct Seg{
	int n,t=0;
	vector<ll>sum,tree;
	vector<ll>done;
	void init(int N){
		n=N;
		sum.resize(n<<2,0);
		tree.resize(n<<2,0);
		done.resize(n<<2,0);
	}
	void push(int node){
		tree[node]+=sum[node]*(t-done[node]);
		done[node]=t;
	}
	int l,r;
	void update(int tar,ll val,ll kat){
		int node=1,left=0,right=n-1;
		while(left<right){
			push(node);
			tree[node]+=kat*val;
			sum[node]+=val;
			node*=2;
			if(tar>mid){
				node++;
				left=mid+1;
			}
			else right=mid;
		}
		push(node);
		tree[node]+=kat*val;
		sum[node]+=val;
	}
	ll qu(bool type,int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return 0;
		if(!type)push(node);
		if(left>=l&&right<=r)return type?sum[node]:tree[node];
		return qu(type,node*2,left,mid)+qu(type,node*2+1,mid+1,right);
	}
	ll query(int left,int right){
		l=left;r=right;
		if(l>r)return 0;
		return qu(false);
	}
	ll top(int left,int right){
		l=left;r=right;
		if(l>r)return 0;
		return qu(true);
	}
};

int n,q;
int arr[200023],nex[200023];
ll pref[200023];
vector<pair<pair<int,int>,ll>>laser;
vector<int>act[200023];
pair<int,pair<int,int>>plan[200023];
int per[200023];
ll ans[200023];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		pref[i]=pref[i-1]+arr[i];
	}
	arr[n+1]=1e9+1;
	for(int i=1;i<=q;i++){
		int t,l,r;cin>>t>>l>>r;
		plan[i]={t,{l,r}};
		per[i]=i;
	}
	sort(per+1,per+q+1,[&](const int &x,const int &y){
		return plan[x].fr<plan[y].fr;
	});
	vector<int>sta={n+1};
	for(int i=n;i>=1;i--){
		while(arr[sta.back()]<=arr[i])sta.pop_back();
		nex[i]=sta.back();
		sta.pb(i);
	}
	sta.clear();
	for(int i=1;i<=n;i++){
		while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back();
		if(sta.size()&&arr[sta.back()]==arr[i]){
			sta.pb(i);
			continue;
		}
		if(sta.size()){
			laser.pb({{i,i-sta.back()},arr[sta.back()]-arr[i]});
			laser.pb({{nex[i],nex[i]-sta.back()},arr[i]-arr[sta.back()]});
		}
		sta.pb(i);
	}
	sort(laser.begin(),laser.end(),[&](const pair<pair<int,int>,ll>&x,const pair<pair<int,int>,ll>&y){
		return x.fr.fr-x.fr.sc<y.fr.fr-y.fr.sc;
	});
	int m=laser.size();
	for(int i=0;i<m;i++){
		act[laser[i].fr.sc].pb(i);
	}
	Seg seg,ye;
	seg.init(m);
	ye.init(n+2);
	int p=1;
	for(int tim=0;p<=q;tim++){
		for(int x:act[tim]){
			seg.update(x,laser[x].sc,laser[x].fr.fr);
			ye.update(laser[x].fr.fr-1,-laser[x].sc,laser[x].fr.fr-1);
		}
		while(p<=q&&plan[per[p]].fr==tim){
			ll &res=ans[per[p]];
			ll left=plan[per[p]].sc.fr,right=plan[per[p]].sc.sc;
			res=pref[right]-pref[left-1];
			res+=ye.top(1,left-1)*(left-1)+ye.top(right+1,n)*(right);
			res+=ye.query(left,right);
			int le,ri;
			int l=0,r=m;
			while(l<r){
				int mi=(l+r)/2;
				if(laser[mi].fr.fr-laser[mi].fr.sc+tim>=left)r=mi;
				else l=mi+1;
			}
			le=l;
			l=-1;r=m-1;
			while(l<r){
				int mi=(l+r+1)/2;
				if(laser[mi].fr.fr-laser[mi].fr.sc+tim<=right)l=mi;
				else r=mi-1;
			}
			ri=l;
			res+=seg.top(0,le-1)*(left-1)+seg.top(ri+1,m-1)*right;
			res+=seg.query(le,ri);
			p++;
		}
		seg.t++;
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
}

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