oj.uz

Submission #612389

# Submission time Handle Problem Language Result Execution time Memory
612389 2022-07-29T13:58:04 Z Augustyn Fire (JOI20_ho_t5) C++14
13 / 100
 569 ms 28220 KB 
#include <bits/stdc++.h>
using namespace std;
int n,q,ciag[200002],pod=262144,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];
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);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&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

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:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d",&ciag[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%d%d%d",&pyta[i].first.first,&pyta[i].second.first,&pyta[i].second.second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Incorrect 4 ms 5440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Incorrect 569 ms 28052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 556 ms 27912 KB Output is correct
3 Correct 549 ms 27724 KB Output is correct
4 Correct 543 ms 28172 KB Output is correct
5 Correct 505 ms 27724 KB Output is correct
6 Correct 556 ms 27912 KB Output is correct
7 Correct 518 ms 27976 KB Output is correct
8 Correct 554 ms 27896 KB Output is correct
9 Correct 546 ms 27740 KB Output is correct
10 Correct 532 ms 27568 KB Output is correct
11 Correct 534 ms 28220 KB Output is correct
12 Correct 565 ms 27952 KB Output is correct
13 Correct 537 ms 28100 KB Output is correct
14 Correct 516 ms 27776 KB Output is correct
15 Correct 544 ms 28084 KB Output is correct
16 Correct 514 ms 27808 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 24664 KB Output is correct
2 Correct 485 ms 24780 KB Output is correct
3 Correct 487 ms 25192 KB Output is correct
4 Correct 522 ms 24968 KB Output is correct
5 Correct 487 ms 24908 KB Output is correct
6 Correct 486 ms 24684 KB Output is correct
7 Correct 497 ms 24988 KB Output is correct
8 Correct 519 ms 24952 KB Output is correct
9 Correct 489 ms 24852 KB Output is correct
10 Correct 523 ms 24832 KB Output is correct
11 Correct 534 ms 24968 KB Output is correct
12 Correct 511 ms 25080 KB Output is correct
13 Correct 476 ms 24864 KB Output is correct
14 Correct 516 ms 24932 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Incorrect 4 ms 5440 KB Output isn't correct
3 Halted 0 ms 0 KB -