제출 #420030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420030		jamezzz	Financial Report (JOI21_financial)	C++17	100 / 100	412 ms	38708 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define INF 1023456789
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

int n,d,p[300005],dp[300005],mn[300005],rt[300005];
deque<ii> dq;
vector<ii> v;

struct node{
	int s,e,m,v;
	node *l,*r;
	node (int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;v=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void up(int x,int nv){
		if(s==x&&e==x){ v=nv;return; }
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=max(l->v,r->v);
	}
	int qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
}*root;

int main(){
	sf("%d%d",&n,&d);
	for(int i=0;i<n;++i){
		sf("%d",&p[i]);
		while(!dq.empty()&&dq.back().fi>=p[i])dq.pop_back();
		dq.push_back(ii(p[i],i));
		while(dq.front().se<=i-d)dq.pop_front();
		if(i>=d-1)mn[i]=dq.front().fi;
		else mn[i]=INF;
	}
	root=new node(0,n-1);
	while(!dq.empty())dq.pop_back();
	for(int i=n-1;i>=0;--i){
		while(!dq.empty()&&dq.front().fi<mn[i])dq.pop_front();
		dq.push_front(ii(mn[i],i));
		//if this is i+d, binary search to find p[i-d]
		if(i-d<0)break;
		if(dq.empty())rt[i-d]=n-1;
		else{
			int lo=0,hi=dq.size()-1,mid,res=n-1;
			while(lo<=hi){
				mid=(lo+hi)/2;
				if(dq[mid].fi<=p[i-d])lo=mid+1;
				else{
					res=dq[mid].se;hi=mid-1;
				}
			}
			rt[i-d]=res;
		}
	}
	/*
	for(int i=0;i<n;++i)pf("%d ",mn[i]);
	pf("\n");
	for(int i=0;i<n;++i)pf("%d ",rt[i]);
	pf("\n");
	*/
	for(int i=0;i<n;++i){
		v.pb(ii(p[i],-i));
	}
	//sort in descending p[i]
	sort(all(v),greater<ii>());
	for(int j=0;j<n;++j){
		int i=-v[j].se;
		if(i+d>n-1){//can take anything after it
			dp[i]=root->qry(i,n-1)+1;
			root->up(i,dp[i]);
			continue;
		}
		
		dp[i]=root->qry(i,rt[i])+1;
		root->up(i,dp[i]);
	}
	int ans=0;
	for(int i=0;i<n;++i){
		ans=max(ans,dp[i]);
	}
	pf("%d\n",ans);
}

/*
7 1
100 600 600 200 300 500 500
*/

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:39:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  sf("%d%d",&n,&d);
      |    ^
Main.cpp:41:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   sf("%d",&p[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