Submission #440605

#	Time	Username	Problem	Language	Result	Execution time	Memory
440605		ogibogi2004	Financial Report (JOI21_financial)	C++14	100 / 100	654 ms	15548 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+6;
set<pair<int,int> >s;
int n,d;
int a[MAXN],k[MAXN];
int tree[4*MAXN];
void update(int l,int r,int idx,int q,int val)
{
	if(l>q)return;
	if(r<q)return;
	if(l==r)
	{
		tree[idx]=val;
		return;
	}
	int mid=(l+r)/2;
	update(l,mid,idx*2,q,val);
	update(mid+1,r,idx*2+1,q,val);
	tree[idx]=max(tree[idx*2],tree[idx*2+1]);
}
int query(int l,int r,int idx,int ql,int qr)
{
	if(l>qr)return 0;
	if(r<ql)return 0;
	if(l>=ql&&r<=qr)return tree[idx];
	int mid=(l+r)/2;
	return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
int maxdp=0;
int main()
{
	cin>>n>>d;
	vector<pair<int,int> >v;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		v.push_back({a[i],-i});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
	{
		int t=-v[i].second;
		//cout<<"%% "<<t<<endl;
		auto it=s.lower_bound({t,-1});
		if(it!=s.begin())
		{
			it--;
			if((*it).second>=t)
			{
				k[t]=(*it).second+d;
				continue;
			}
		}
		it=s.lower_bound({t,-1});
		bool flag1=0,flag2=0;
		int l1,r1,l2,r2;
		if(it!=s.end()&&(*it).first-t<=d)
		{
			l2=(*it).first;
			r2=(*it).second;
			flag1=1;
		}
		if(it!=s.begin())
		{
			it--;
			if(t-(*it).second<=d)
			{
				l1=(*it).first;
				r1=(*it).second;
				flag2=1;
			}
		}
		if(flag1&&flag2)
		{
			k[t]=r2+d;
			s.erase({l1,r1});
			s.erase({l2,r2});
			s.insert({l1,r2});
		}
		else if(flag2)
		{
			k[t]=t+d;
			s.erase({l1,r1});
			s.insert({l1,t});
		}
		else if(flag1)
		{
			k[t]=r2+d;
			s.erase({l2,r2});
			s.insert({t,r2});
		}
		else
		{
			k[t]=t+d;
			s.insert({t,t});
		}
		/*for(auto xd:s)
		{
			cout<<xd.first<<" "<<xd.second<<endl;
		}*/
	}
	reverse(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
	{
		int idx=-v[i].second;
		k[idx]=min(k[idx],n);
		int dp=query(1,n,1,idx,k[idx])+1;
		maxdp=max(maxdp,dp);
		//cout<<idx<<" "<<k[idx]<<" "<<dp<<endl;
		update(1,n,1,idx,dp);
	}
	cout<<maxdp<<endl;
return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~
Main.cpp:104:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~

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