Submission #612475

#	Time	Username	Problem	Language	Result	Execution time	Memory
612475		Augustyn	Fire (JOI20_ho_t5)	C++14	100 / 100	629 ms	30692 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
int n,q,pod=1,nale[200001],napr[200001];
pair<pair<int,int>,pair<int,int>>pyta[200001];
int drzemax[1000001],pocz,kon;
int itmi,itma,gmi,gma,gze;
pair<int,int>zmmin[200001],zmmax[200001],zmzer[200001];
stack<int>stos;
long long odp[200001],drze[1000001][2],ciag[200002];
int znajdz(int ter,int odte,int dote)
{
	if(ter>=pod)
		return ter-pod;
	if(odte>=pocz&&dote<=kon)
	{
		if(drzemax[((ter<<1)^1)]>=drzemax[(ter<<1)])
			return znajdz(((ter<<1)^1),((odte+dote)>>1)+1,dote);
		else
			return znajdz((ter<<1),odte,((odte+dote)>>1));
	}
	int pom1=0,pom2=0;
	if(((odte+dote)>>1)+1<=kon)
		pom1=znajdz(((ter<<1)^1),((odte+dote)>>1)+1,dote);
	if(((odte+dote)>>1)>=pocz)
		pom2=znajdz((ter<<1),odte,((odte+dote)>>1));
	if(ciag[pom1]>=ciag[pom2])
		return pom1;
	else
		return pom2;
}
long long naprze(int odte,int dote,long long te)
{
	long long ret=0;
	odte+=pod;
	dote+=pod;
	while(odte<dote)
	{
		if(odte%2==0)
			odte>>=1;
		else
		{
			ret+=drze[odte][0]+drze[odte][1]*te;
			odte>>=1;
			++odte;
		}
		if(dote%2==1)
			dote>>=1;
		else
		{
			ret+=drze[dote][0]+drze[dote][1]*te;
			dote>>=1;
			--dote;
		}
	}
	if(odte==dote)
	{
		ret+=drze[dote][0]+drze[dote][1]*te;
	}
	return ret;
}
int main()
{	
	scanf("%d%d",&n,&q);
	while(pod<=n)
		pod<<=1;
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&ciag[i]);
		drze[i+pod][0]=ciag[i];
		drze[i+pod][1]=ciag[i];
		drzemax[i+pod]=ciag[i];
		while(!stos.empty())
		{
			if(ciag[stos.top()]>ciag[i])
				break;
			stos.pop();
		}
		if(!stos.empty())
		nale[i]=stos.top();
		stos.push(i);
	}
	while(!stos.empty())
		stos.pop();
	ciag[n+1]=1000000001;
	stos.push(n+1);
	for(int i=n;i>0;--i)
	{
		while(!stos.empty())
		{
			if(ciag[stos.top()]>=ciag[i])
				break;
			stos.pop();
		}
		napr[i]=stos.top()-1;
		stos.push(i);
		zmmin[itmi].second=i;
		zmmin[itmi].first=napr[i]-i;
		++itmi;
		if(nale[i])
		{
			zmmax[itma].second=i;
			zmmax[itma].first=i-nale[i];
			zmzer[itma].second=i;
			zmzer[itma].first=napr[i]-nale[i];
			++itma;
		}
	}
	for(int i=pod-1;i>=0;--i)
	{
		drzemax[i]=max(drzemax[(i<<1)],drzemax[((i<<1)^1)]);
		drze[i][0]=drze[(i<<1)][0]+drze[((i<<1)^1)][0];
		drze[i][1]=drze[(i<<1)][1]+drze[((i<<1)^1)][1];
	}
	for(int i=0;i<q;++i)
	{
		scanf("%d%d%d",&pyta[i].first.first,&pyta[i].second.first,&pyta[i].second.second);
		pyta[i].first.second=i;
	}
	sort(pyta,pyta+q);
	sort(zmmin,zmmin+itmi);
	sort(zmmax,zmmax+itma);
	sort(zmzer,zmzer+itma);
	for(int i=0;i<q;++i)
	{
		for(int j=gmi;j<itmi;++j)
		{
			if(zmmin[j].first>pyta[i].first.first)
				break;
			++gmi;
			int ter=zmmin[j].second+pod;
			drze[ter][0]-=ciag[ter-pod]*(ter-pod);
			drze[ter][1]-=ciag[ter-pod];
			drze[ter][0]+=ciag[ter-pod]*napr[ter-pod];
			ter/=2;
			while(ter)
			{
				drze[ter][0]=drze[(ter<<1)][0]+drze[((ter<<1)^1)][0];
				drze[ter][1]=drze[(ter<<1)][1]+drze[((ter<<1)^1)][1];
				ter>>=1;
			}
		}
		for(int j=gma;j<itma;++j)
		{
			if(zmmax[j].first>pyta[i].first.first)
				break;
			++gma;
			int ter=zmmax[j].second+pod;
			drze[ter][0]+=ciag[ter-pod]*(ter-pod-1);
			drze[ter][1]-=ciag[ter-pod];
			drze[ter][0]-=ciag[ter-pod]*nale[ter-pod];
			ter/=2;
			while(ter)
			{
				drze[ter][0]=drze[(ter<<1)][0]+drze[((ter<<1)^1)][0];
				drze[ter][1]=drze[(ter<<1)][1]+drze[((ter<<1)^1)][1];
				ter>>=1;
			}

		}
		for(int j=gze;j<itma;++j)
		{
			if(zmzer[j].first>pyta[i].first.first)
				break;
			++gze;
			int ter=zmzer[j].second+pod;

			drze[ter][0]=0;
			drze[ter][1]=0;
			drze[ter][0]=0;
			ter/=2;
			while(ter)
			{
				drze[ter][0]=drze[(ter<<1)][0]+drze[((ter<<1)^1)][0];
				drze[ter][1]=drze[(ter<<1)][1]+drze[((ter<<1)^1)][1];
				ter>>=1;
			}
		}
		pocz=max(1,pyta[i].second.first-pyta[i].first.first)+pod;
		kon=pyta[i].second.first+pod;
		int p1=znajdz(1,pod,pod+pod-1);
		pocz=max(1,pyta[i].second.second-pyta[i].first.first)+pod;
		kon=pyta[i].second.second+pod;
		int p2=znajdz(1,pod,pod+pod-1);
		if(p1==p2)
		odp[pyta[i].first.second]=(pyta[i].second.second-pyta[i].second.first+1)*ciag[p1];
		else
		{
			odp[pyta[i].first.second]=naprze(p1+1,p2-1,pyta[i].first.first);
			odp[pyta[i].first.second]+=(min(napr[p1],p1+pyta[i].first.first)-pyta[i].second.first+1)*ciag[p1];
			if(nale[p2])
			odp[pyta[i].first.second]+=(pyta[i].second.second-max(p2-1,nale[p2]+pyta[i].first.first))*ciag[p2];
			else
			odp[pyta[i].first.second]+=(pyta[i].second.second-p2+1)*ciag[p2];
		}
	}
	for(int i=0;i<q;++i)
		printf("%lld\n",odp[i]);
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
ho_t5.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%lld",&ciag[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   scanf("%d%d%d",&pyta[i].first.first,&pyta[i].second.first,&pyta[i].second.second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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