Submission #536097

#	Time	Username	Problem	Language	Result	Execution time	Memory
536097		iliaM	Financial Report (JOI21_financial)	C++17	19 / 100	384 ms	14448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 3e5 + 10;

int n, last[N], dp[N], mx[N], d, b[N];
pair<int, int> idx[N];
long long a[N];

void compress() {
	static long long tmp[N];
	memcpy(tmp, a, sizeof(a));
	sort(tmp, tmp + n);
	int m = unique(tmp, tmp + n) - tmp;
	for (int i = 0; i < n; ++i) {
		a[i] = lower_bound(tmp, tmp + m, a[i]) - tmp;
	}
}

int t[N << 1];

void build(int *shit) {
	for (int i = 0; i < n; ++i) {
		t[i + n] = shit[i];
	}
	for (int i = n - 1; i > 0; --i) {
		t[i] = max(t[i << 1], t[i << 1 | 1]);
	}
}

void update(int i, int x) {
	for (t[i += n] = x; i > 1; i >>= 1) {
		t[i >> 1] = max(t[i], t[i ^ 1]);
	}
}

int query(int u, int v) {
	int res = -1e9;
	for (u += n, v += n; u < v; u >>= 1, v >>= 1) {
		if (u & 1) {
			res = max(res, t[u++]);
		}
		if (v & 1) {
			res = max(res, t[--v]);
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
		
	cin >> n >> d;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	compress();
	for (int i = 0; i < n; ++i) {
		idx[i] = {a[i], -i};
		b[i] = -a[i];
	}
	
	fill(t, t + 2 * N, -1e9);
	build(b);
	for (int i = 0; i < n; ++i) {
		mx[i] = -query(max(0, i - d), i + 1);
		//cout << mx[i] << ' ';
	}
	//cout << '\n';
	build(mx);
	for (int i = 0; i < n; ++i) {
		int low = i + d + 1, high = n - 1;
		//cerr << low << ' ' << high << '\n';
		while (high - low > 0) {
			int mid = (high + low) >> 1;
			if (query(i + d + 1, mid + 1) >= a[i]) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}
		//cerr << min(n, low) << '\n';
		last[i] = min(n, low);
	}

	sort(idx, idx + n, greater<pair<int, int>>());

	fill(t, t + 2 * N, -1e9);
	for (int j = 0; j < n; ++j) {
		int i = -idx[j].second;
		dp[i] = max(query(i + 1, last[i]), 0) + 1;
		update(i, dp[i]);
	}
	/*for (int i = 0; i < n; ++i) {
		cout << -b[i] << ' ';
	}
	cout << '\n';
	for (int i = 0; i < n; ++i) {
		cout << last[i] << ' ';
	}
	cout << '\n';
	for (int i = 0; i < n; ++i) {
		cout << dp[i] << ' ';
	}
	cout << '\n';*/
	cout << *max_element(dp, dp + n);
}

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