oj.uz

Submission #612313

# Submission time Handle Problem Language Result Execution time Memory
612313 2022-07-29T12:59:47 Z Augustyn Fire (JOI20_ho_t5) C++14
13 / 100
 706 ms 28656 KB 
#include <bits/stdc++.h>
using namespace std;
// #define ti first.first
// #define nrp first.second
// #define le second.first
// #define pr second.second
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-1-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:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
ho_t5.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d",&ciag[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   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 5 ms 5460 KB Output is correct
2 Incorrect 4 ms 5460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5460 KB Output is correct
2 Incorrect 666 ms 28524 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 5 ms 5460 KB Output is correct
2 Correct 640 ms 28336 KB Output is correct
3 Correct 582 ms 27936 KB Output is correct
4 Correct 585 ms 28656 KB Output is correct
5 Correct 623 ms 28000 KB Output is correct
6 Correct 583 ms 28128 KB Output is correct
7 Correct 586 ms 28264 KB Output is correct
8 Correct 587 ms 28248 KB Output is correct
9 Correct 663 ms 28056 KB Output is correct
10 Correct 574 ms 27780 KB Output is correct
11 Correct 610 ms 28596 KB Output is correct
12 Correct 570 ms 28180 KB Output is correct
13 Correct 618 ms 28512 KB Output is correct
14 Correct 601 ms 28064 KB Output is correct
15 Correct 630 ms 28436 KB Output is correct
16 Correct 706 ms 28068 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 24692 KB Output is correct
2 Correct 566 ms 24636 KB Output is correct
3 Correct 549 ms 25232 KB Output is correct
4 Correct 680 ms 24840 KB Output is correct
5 Correct 607 ms 24844 KB Output is correct
6 Correct 564 ms 24688 KB Output is correct
7 Correct 579 ms 24980 KB Output is correct
8 Correct 534 ms 24928 KB Output is correct
9 Correct 555 ms 24940 KB Output is correct
10 Correct 645 ms 24844 KB Output is correct
11 Correct 613 ms 24988 KB Output is correct
12 Correct 528 ms 24984 KB Output is correct
13 Correct 550 ms 24916 KB Output is correct
14 Correct 524 ms 25032 KB Output is correct

Subtask #5
0 / 80.0

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