Submission #429285

#	Time	Username	Problem	Language	Result	Execution time	Memory
429285		Pyqe	Financial Report (JOI21_financial)	C++14	100 / 100	838 ms	45508 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,d;
pair<long long,long long> a[300069];

struct segtree
{
	long long l,r,mx,mx2,lz;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		mx=0;
		mx2=0;
		lz=0;
		if(l<r)
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void blc()
	{
		long long ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mx+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(long long lh,long long rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mx+=w;
			lz+=w;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	void ins(long long x,long long w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			mx2=w;
		}
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ins(x,w);
			}
			mx2=max(p[0]->mx2,p[1]->mx2);
		}
	}
	long long bl(long long lh,long long w)
	{
		if(r<lh)
		{
			return r;
		}
		else if(l>=lh)
		{
			if(mx<w)
			{
				return r;
			}
			else if(l==r)
			{
				return l-1;
			}
			else
			{
				blc();
				return p[p[0]->mx<w]->bl(lh,w);
			}
		}
		else
		{
			long long k;
			
			blc();
			k=p[0]->bl(lh,w);
			if(k<p[0]->r)
			{
				return k;
			}
			else
			{
				return p[1]->bl(lh,w);
			}
		}
	}
	long long qr(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return 0;
		}
		else if(l>=lh&&r<=rh)
		{
			return mx2;
		}
		else
		{
			return max(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
		}
	}
}
sg;

int main()
{
	long long i,k,l,w,z=0;
	
	scanf("%lld%lld",&n,&d);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&k);
		a[i]={-k,i};
	}
	sort(a+1,a+n+1);
	sg.bd(1,n);
	for(i=1;i<=n;i++)
	{
		k=a[i].sc;
		l=sg.bl(k+d,d)+1;
		w=sg.qr(k+1,l)+1;
		z=max(z,w);
		sg.ud(k,k+d-1,1);
		sg.ins(k,w);
	}
	printf("%lld\n",z);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%lld%lld",&n,&d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%lld",&k);
      |   ~~~~~^~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35