제출 #1153132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153132		WH8	Financial Report (JOI21_financial)	C++20	5 / 100	504 ms	52284 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long 
#define f first
#define s second
#define pb push_back
#define ld long double
#define pll pair<int, int>
#define mp make_pair

int n,d;
int a[300005];

struct node{
	int s, e, m, mnocc, mnoi, val, prop;
	node *l, *r;
	node(int S, int E){
		s=S, e=E, m=(s+e)>>1, mnocc=1e9, mnoi=s, val=0, prop=-1;
		if (s!=e){
			l=new node(s, m);
			r=new node(m+1,e);
		}
	}
	void pf(){
		if (prop == -1)return;
		if(val > 0) mnocc=prop;
		if(s!=e)l->prop=prop, r->prop=prop;
		prop=-1;
	}
	void upd(int X, int VAL, int MNOCC){
		if(s==e){
			
			if(MNOCC != 1e9) val=max(val, VAL);
			else val=VAL; 
			
			mnocc=MNOCC;
			return;
		}
		pf();
		if(X <= m)l->upd(X,VAL, MNOCC);
		else r->upd(X, VAL,MNOCC);
		val=max(l->val, r->val);
		if(l->mnocc <= r->mnocc){
			mnocc=l->mnocc;
			mnoi=l->mnoi;
		}
		else{
			mnocc=r->mnocc;
			mnoi=r->mnoi;
		}
	}
	void occupd(int S, int E, int MNOCC){
		if (S==s and E==e){
			prop=MNOCC;
			if(val > 0) mnocc=MNOCC;
			return;
		}
		if (S > m) return r->occupd(S,E,MNOCC);
		else if(E<=m)return l->occupd(S,E,MNOCC);
		pf();
		l->occupd(S,m,MNOCC),r->occupd(m+1,E,MNOCC);
		if(l->mnocc <= r->mnocc){
			mnocc=l->mnocc;
			mnoi=l->mnoi;
		}
		else{
			mnocc=r->mnocc;
			mnoi=r->mnoi;
		}
	}
	int qry(int S, int E){
		pf();
		if(E<S)return 0;
		
		if (s==S and e==E)return val;
		if(E<=m)return l->qry(S,E);
		if(S>m) return r->qry(S,E);
		return max(l->qry(S,m), r->qry(m+1,E));
	}
};

signed main(){
	cin>>n>>d;
	vector<int> disc;
	for(int i=0;i<n;i++){
		cin>>a[i];
		disc.pb(a[i]);
	}
	sort(disc.begin(),disc.end());
	disc.erase(unique(disc.begin(),disc.end()),disc.end());
	for(int i=0;i<n;i++){
		a[i]=lower_bound(disc.begin(),disc.end(),a[i])-disc.begin();
		//~ cout<<a[i]<<endl;
	}
	//~ return 0;
	node * root=new node(0, n);
	for(int i=0;i<n;i++){
		//~ cout<<"----------- " << i << " ------------\n";
		int mnocc = root->mnocc;
		//~ printf("mnocc %lld found at mnoi %lld\n", mnocc, root->mnoi);

		while(mnocc<i-d){
			//~ printf("mnocc %lld found at mnoi %lld, deleting\n", mnocc, root->mnoi);
			root->upd(root->mnoi, 0, 1e9);
			mnocc=root->mnocc;
		}
		int mxr=root->qry(0, a[i]-1);
		//~ printf("mxr is %lld\n",mxr);
		root->upd(a[i], mxr+1, i);
		root->occupd(a[i]+1, n, i);
		if(i ==n-1)cout<<root->qry(0, n);
	}
}

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