Submission #1182368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182368		catch_me_if_you_can	Financial Report (JOI21_financial)	C++20	100 / 100	422 ms	35664 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 3e5+5;
const int INF = 1e17;

int D;
set<int> active;
vector<int> pa(MX);
int L[MX];

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}

void merge(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u == v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	L[v] = min(L[v], L[u]);
	pa[v]+=pa[u];
	pa[u] = v;
	return;
}

void add(int x)
{
	pa[x] = -1;
	L[x] = x; 
	auto it = (active.insert(x)).first;
	if(next(it) != active.end())
	{
		int xp = *next(it);
		if(xp <= (x+D))
			merge(x, xp);
	}
	if(it != active.begin())
	{
		int xp = *prev(it);
		if(xp >= (x-D))
			merge(x, xp);
	}
	return;
}

struct seg_tree
{
	vector<int> tree;
	void init(int n)
	{
		tree.assign(4*n+10, 1);
		return;
	}
	void upd(int p, int val, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = val;
			return;
		}
		int m = (l+r)/2;
		if(p <= m)
			upd(p, val, 2*id, l, m);
		else
			upd(p, val, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1]);
		return;
	}
	int Q(int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return -INF;
		if(ql <= l && r <= qr)
			return tree[id];
		int m = (l+r)/2;
		int a1 = Q(ql, qr, 2*id, l, m);
		int a2 = Q(ql, qr, 2*id+1, m+1, r);
		return max(a1, a2); 
	}
};

signed main()
{
	fast();
	int n; cin >> n >> D;
	vector<in> a(n+1);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i][0];
		a[i][1] = -i;
	}
	sort(a.begin()+1, a.end());
	seg_tree work; work.init(n);
	int ans = 1;
	int dp[n+1];
	for(int j = 1; j <= n; j++)
	{
		int i = -a[j][1];
		add(i);
		int g = L[leader(i)];
		if(g == i)
		{
			dp[i] = 1;
			continue;
		}
		dp[i] = work.Q(g, i-1, 1, 1, n) + 1;
		ans = max(ans, dp[i]);
		work.upd(i, dp[i], 1, 1, n);
	}
	//cout << "\n";
	cout << ans << "\n";
	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