Submission #727190

#	Time	Username	Problem	Language	Result	Execution time	Memory
727190		NeroZein	Financial Report (JOI21_financial)	C++17	5 / 100	272 ms	22896 KiB

Main

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 300005;

int n, d;
int a[N];
int dp[N]; 
int seg[N << 1];
vector<int> in[N];

void upd (int nd, int l, int r, int p, int v) {
	if (l == r) {
		seg[nd] = v;
		return;
	}
	int mid = (l + r) >> 1;
	int rs = nd + ((mid - l + 1) << 1);
	if (p <= mid) {
		upd(nd + 1, l, mid, p, v);
	} else {
		upd(rs, mid + 1, r, p, v); 
	}
	seg[nd] = max(seg[nd + 1], seg[rs]); 
}
void upd (int p, int v) {
	upd(0, 0, n, p, v); 
}

int qry (int nd, int l, int r, int s, int e) {
	if (l >= s && r <= e) {
		return seg[nd];
	}
	int mid = (l + r) >> 1;
	int rs = nd + ((mid - l + 1) << 1);
	if (mid >= e) {
		return qry(nd + 1, l, mid, s, e);
	} else {
		if (mid < s) {
			return qry(rs, mid + 1, r, s, e);
		} else {
			return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
		}
	}
}
int qry (int l, int r) {
	l = max(l, 0); 
	return qry(0, 0, n, l, r); 
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> d;
	vector<int> b(n); 
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b.begin(), b.end()); 
	b.resize(unique(b.begin(), b.end()) - b.begin()); 
	for (int i = 0; i < n; ++i) {
		a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin(); 
		in[a[i]].push_back(i); 
	}
	int ans = 1; 
	for (int i = 0; i < n; ++i) {
		for (int j : in[i]) {
			dp[j] = qry(j - d, j) + 1;
			ans = max(ans, dp[j]);
		}
		for (int j : in[i]) {
			upd(j, dp[j]);
		}
	}
	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