Submission #419776

#	Time	Username	Problem	Language	Result	Execution time	Memory
419776		kshitij_sodani	Financial Report (JOI21_financial)	C++14	100 / 100	1203 ms	56736 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,d;
llo it[300001];
llo dp[7001][7001];






llo tree[4*300001];
llo tree2[4*300001];

llo lazy[4*300001];
llo dp2[300001];
void push(llo no,llo l,llo r){
	if(lazy[no]){
		tree[no]=0;
		if(l<r){
			lazy[no*2+1]=lazy[no];
			lazy[no*2+2]=lazy[no];
		}


		lazy[no]=0;
	}

}
void build(llo no,llo l,llo r){
	if(l==r){
		tree[no]=0;
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo j){
	push(no,l,r);
	if(r<aa or l>bb){
		return ;
	}
	if(aa<=l and r<=bb){
		if(j==0){
			lazy[no]=1;
			push(no,l,r);
		}
		else{
			tree[no]=max(tree[no],j);
		}
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,j);
		update(no*2+2,mid+1,r,aa,bb,j);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	push(no,l,r);
	if(r<aa or l>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>d;
	llo ma=-1;
	//llo ans=0;
	map<llo,llo> sss;
	for(llo i=0;i<n;i++){
		
		cin>>it[i];
		sss[it[i]]++;
	//	dp[i][
/*		if(it[i]>ma){
			ans++;
		}
		ma=max(ma,it[i]);*/
	}
	map<llo,llo> tt;
	llo ind5=-1;
	for(auto j:sss){
		ind5++;
		tt[j.a]=ind5;
	}
	vector<pair<llo,llo>> kk;
	for(llo i=0;i<n;i++){
		it[i]=tt[it[i]];

	}

	llo ans=0;
	//build(0,0,n-1);
	/*for(llo i=0;i<n;i++){
		tree[i]={{0,n},i};
	}*/
	deque<pair<llo,llo>> xx;

	/*for(llo i=0;i<n;i++){
		cout<<it[i]<<":";
	}
	cout<<endl;*/
	for(llo i=0;i<n;i++){
		//le=i;
		while(xx.size()){
			if(xx.front().b<=i-d){
				xx.pop_front();
			}
			else{
				break;
			}
		}
		//cout<<i-d<<endl;
		while(xx.size()){
			if(xx.back().a>=it[i]){
				xx.pop_back();
			}
			else{
				break;
			}
		}
		xx.pb({it[i],i});


		/*}
		for(llo j=0;j<n;j++){
			if(tree[j].a.b<i-d){
				tree[j]={{(llo)0,n},j};
			}
		}*/
	/*	for(llo j=it[i];j<n;j++){
			tree[j].a.b=max(tree[j].a.b,i);
		}*/
		//update2(0,0,n-1,it[i],n-1,i);

		//if(it[i]>0){
			//llo x=0;
			llo x=0;
			if(it[i]>0){
				x=query(0,0,n-1,0,it[i]-1);
				/*for(llo j=0;j<it[i];j++){
					x=max(x,tree[j].a.a);
				}*/
				//x=query(0,0,n-1,0,it[i]-1);
			}
			//update(0,0,n-1,it[i],x+1);
			update(0,0,n-1,it[i],it[i],x+1);
			//tree[it[i]]=max(tree[it[i]],{{x+1,i},it[i]});
			ans=max(ans,x+1);

			if(i>=d){
				//cout<<i<<":"<<xx.front().a<<endl;
				if(xx.front().a>0){
					update(0,0,n-1,0,xx.front().a-1,0);
				}
				/*for(llo j=0;j<xx.front().a;j++){
					tree[j]={{(llo)0,n},j};
				}*/
			}
	}

	cout<<ans<<endl;
	//cout<<ans<<endl;





	return 0;
}
 

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:87:6: warning: unused variable 'ma' [-Wunused-variable]
   87 |  llo ma=-1;
      |      ^~

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