Submission #205385

#	Time	Username	Problem	Language	Result	Execution time	Memory
205385		TadijaSebez	Fire (JOI20_ho_t5)	C++11	100 / 100	409 ms	22008 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=200050;
struct BIT{
	ll sum[N];
	void init(){for(int i=0;i<N;i++)sum[i]=0;}
	BIT(){init();}
	void Set(int i,ll f){for(i++;i<N;i+=i&-i)sum[i]+=f;}
	ll Get(int i){ll ans=0;for(i++;i;i-=i&-i)ans+=sum[i];return ans;}
}SUM,MUL,STK;
int a[N];
vector<pair<int,int>> Qs[N];
int stk[N],top;
ll ans[N];
void AddD(int t,ll f){
	//printf("AddD %i %lld\n",t,f);
	SUM.Set(t,-(ll)t*f);
	MUL.Set(t,f);
}
ll Get(int t){
	//printf("t:%i mul:%lld sum:%lld\n",t,MUL.Get(t),SUM.Get(t));
	return (t+1)*MUL.Get(t)+SUM.Get(t);
}
int main(){
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);
	for(int i=1,t,l,r;i<=q;i++)scanf("%i %i %i",&t,&l,&r),Qs[r].pb({i,t}),Qs[l-1].pb({-i,t});
	for(int i=1;i<=n;i++){
		while(top && a[stk[top]]<=a[i]){
			AddD(i-stk[top],-a[stk[top]]);
			if(top>1)AddD(i-stk[top-1],a[stk[top]]);
			if(top>1)STK.Set(top,-(ll)(stk[top]-stk[top-1])*a[stk[top]]);
			top--;
		}
		AddD(0,a[i]);
		if(top>0)AddD(i-stk[top],-a[i]);
		stk[++top]=i;
		if(top>1)STK.Set(top,(ll)(stk[top]-stk[top-1])*a[stk[top]]);
		for(auto Q:Qs[i]){
			int t=Q.second;
			ll now=Get(t);
			//printf("Get: %lld ",now);
			int hi=top,lo=1,mid,pos=top;
			while(hi>=lo){
				mid=hi+lo>>1;
				if(i-stk[mid]<=t)pos=mid,hi=mid-1;
				else lo=mid+1;
			}
			now-=STK.Get(top)-STK.Get(pos);
			//printf("%lld ",now);
			now-=(ll)a[stk[pos]]*(t-(i-stk[pos]));
			int id=abs(Q.first);
			//printf("i:%i t:%i now:%lld\n",i,t,now);
			if(Q.first<0)ans[id]-=now;
			else ans[id]+=now;
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=hi+lo>>1;
         ~~^~~
ho_t5.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:29:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&a[i]);
                       ~~~~~^~~~~~~~~~~~
ho_t5.cpp:30:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1,t,l,r;i<=q;i++)scanf("%i %i %i",&t,&l,&r),Qs[r].pb({i,t}),Qs[l-1].pb({-i,t});
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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