Submission #1092521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092521		hungnt	Financial Report (JOI21_financial)	C++14	100 / 100	425 ms	36372 KiB

Main

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

#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using ar2 = array<int,2>;
const int mxN = (int)3e5+10;
int n, d, dp[mxN], seg[mxN*2];
int a[mxN], p[mxN], sz[mxN], mn[mxN];

int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
void unionSet(int i, int j){
	int x = findSet(i), y = findSet(j);
	if(x==y) return;
	if(sz[x]<sz[y])swap(x,y);
	p[y] = x, sz[x]+=sz[y];
	mn[x]=mn[y]=min(mn[x],mn[y]);
}

void upd(int x, int v, int p=0, int l=1, int r=n){
	if(l==r){ seg[p]=v; return; }
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,v,p+1,l,mid);
	else upd(x,v,rp,mid+1,r);
	seg[p] = max(seg[p+1],seg[rp]);
}

int query(int i, int j, int p=0, int l=1, int r=n){
	if(i>r or j<l or i>j) return 0;
	if(i<=l and r<=j) return seg[p];
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	return max(query(i,j,p+1,l,mid),query(i,j,rp,mid+1,r));
}

int32_t main(){
	cin >> n >> d;
	for(int i = 1; i <= n; i++)
		cin >> a[i],p[i]=i,sz[i]=1,mn[i]=i;
	vector<int> ord(n,0); iota(all(ord),1);
	sort(all(ord),[&](int i, int j){
		if(a[i]==a[j]) return i>j;
		return a[i]<a[j];
	});
	set<int> pos;
	int ans = 0;
	for(auto i : ord){
		auto itr = pos.lower_bound(i);
		if(itr!=end(pos))
			if(*itr-i<=d) unionSet(i,*itr);
		if(itr!=begin(pos)){ itr--;
			if(i-*itr<=d) unionSet(*itr,i);
		}
		pos.insert(i);
		dp[i] = max(1ll, query(mn[findSet(i)],i-1)+1);
		ans=max(ans,dp[i]); upd(i,dp[i]);
	}
	cout << ans;
}

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