Submission #1108571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108571		pcc	Financial Report (JOI21_financial)	C++17	5 / 100	245 ms	34316 KiB

Main

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tiii tuple<int,int,int>
#define tlll tuple<ll,ll,ll>

const int mxn = 6e5+10;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	int seg[mxn*4];
	void modify(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now] = v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = max(seg[ls],seg[rs]);
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs
#undef mid
} seg;

int N,D;
bitset<mxn> active;

struct DSU{
	int dsu[mxn],sz[mxn];
	int lp[mxn],rp[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
		iota(rp,rp+mxn,0);
		iota(lp,lp+mxn,0);
		fill(sz,sz+mxn,1);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
		lp[a] = min(lp[a],lp[b]);
		rp[a] = max(rp[a],rp[b]);
		return;
	}
} dsu;

set<int> st;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>D;
	vector<pii> v(N);
	for(int i = 1;i<=N;i++)cin>>v[i-1].fs,v[i-1].sc = i;
	sort(v.begin(),v.end(),[](pii a,pii b){return a.fs == b.fs?a.sc<b.sc:a.fs>b.fs;});
	for(int i = N+1;i<N*2;i++){
		active[i+1] = active[i] = 1,dsu.onion(i,i+1);
	}
	st.insert(N+1);
	int ans = 0;
	for(auto &[_,now]:v){
		auto it = st.upper_bound(now);
		int tans = seg.getval(0,1,N*2,now,*it+D)+1;
		ans = max(ans,tans);
		seg.modify(0,1,N*2,now,tans);
		active[now] = true;
		if(active[now-1])dsu.onion(now,now-1);
		if(active[now+1])dsu.onion(now,now+1);
		int rt = dsu.root(now);
		if(dsu.sz[rt]>=D)st.insert(dsu.lp[rt]);
	}
	cout<<ans<<'\n';
	return 0;
}

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