Submission #533615

#	Time	Username	Problem	Language	Result	Execution time	Memory
533615		codr0	Financial Report (JOI21_financial)	C++14	100 / 100	409 ms	25024 KiB

Main

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
const int N=3e5+4;
int seg[4*N];
bool lazy[4*N];

	void shift(int id){
		if(!lazy[id]) return;
		lazy[2*id]=lazy[2*id+1]=1;
		lazy[id]=0;
		seg[id]=0;
		seg[2*id]=0;
		seg[2*id+1]=0;
	}

	int get(int id,int l,int r,int st,int en){
		if(en==st) return 0;
		if(st>=r||en<=l) return 0;
		if(st<=l&&en>=r) return seg[id];
		shift(id);
		int mid=(r+l)/2;
		return max(get(2*id,l,mid,st,en),get(2*id+1,mid,r,st,en));
	}

	void upd(int id,int l,int r,int ind,int X){
		if(ind<l||ind>=r) return;
		if(l+1==r){
			seg[id]=max(seg[id],X);
			return;
		}
		shift(id);
		int mid=(r+l)/2;
		upd(2*id,l,mid,ind,X);
		upd(2*id+1,mid,r,ind,X);
		seg[id]=max(seg[2*id],seg[2*id+1]);
	}

	void upd0(int id,int l,int r,int st,int en){
		if(st>=r||en<=l) return;
		if(st<=l&&en>=r){
			seg[id]=0;
			lazy[id]=1;
			return;
		}
		shift(id);
		int mid=(r+l)/2;
		upd0(2*id,l,mid,st,en);
		upd0(2*id+1,mid,r,st,en);
		seg[id]=max(seg[2*id],seg[2*id+1]);
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n,D; cin>>n>>D;
	vector<pii> vc;
	int a[n+1];
	FOR(i,1,n){
		int x0; cin>>x0;
		vc.pb({x0,i});
	}
	sort(all(vc));
	int pr=0;
	FOR(i,0,SZ(vc)-1){
		if(i==0||vc[i].F!=vc[i-1].F) pr++;
		a[vc[i].S]=pr;
	}
	set<pii> st;
	FOR(i,1,n){
		int X=get(1,1,n+1,1,a[i]);
		upd(1,1,n+1,a[i],X+1);
		if(i==n){
			int Y=get(1,1,n+1,a[i],n+1);
			cout<<max(Y,X+1)<<'\n';
			return 0;
		}
		st.insert({a[i],i});
		if(SZ(st)>D){
			st.erase({a[i-D],i-D});
			int mn=(*st.begin()).F;
			upd0(1,1,n+1,1,mn-1);
		}
	}

	return 0;
	}

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