Submission #870042

#	Time	Username	Problem	Language	Result	Execution time	Memory
870042		serifefedartar	Financial Report (JOI21_financial)	C++17	100 / 100	420 ms	27080 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 3e5 + 100;

vector<int> A;
int par[MAXN], leftmost[MAXN];
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}

void unite(int a, int b) {
	a = find(a), b = find(b);	
	if (a == b)
		return ;
	par[b] = a;
	leftmost[a] = min(leftmost[a], leftmost[b]);
}

int sg[4*MAXN];
void update(int k, int a, int b, int plc, int val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k] = val;
		return ;
	}
	update(2*k, a, (a+b)/2, plc, val);
	update(2*k+1, (a+b)/2+1, b, plc, val);
	sg[k] = max(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b, int q_l, int q_r) {
	if (b < q_l || a > q_r)
		return 0;
	if (q_l <= a && b <= q_r)
		return sg[k];
	return max(query(2*k, a, (a+b)/2, q_l, q_r),
				query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

vector<int> ind;
int main() {
	fast
	int N, D;
	cin >> N >> D;

	A = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		par[i] = i, leftmost[i] = i; 
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	for (int i = 1; i <= N; i++)
		ind.push_back(i);
	sort(ind.begin(), ind.end(), [&](int a, int b) {
		return (A[a] < A[b] || (A[a] == A[b] && a > b));
	});

	set<int> st;
	for (auto u : ind) {
		auto x = st.lower_bound(u);
		if (x != st.end()) {
			int p = *x;
			if (abs(p - u) <= D)
				unite(p, u);
		}
		if (x != st.begin()) {
			x--;
			int p = *x;
			if (abs(p - u) <= D)
				unite(p, u);
		}
		st.insert(u);

		int fnd = leftmost[find(u)];
		int dp = max(1, (fnd <= u - 1 ? query(1, 1, N, fnd, u - 1) + 1 : 0));
		update(1, 1, N, u, dp);
	}
	cout << query(1, 1, N, 1, N) << "\n";
}

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