Submission #419611

#	Time	Username	Problem	Language	Result	Execution time	Memory
419611		Kevin_Zhang_TW	Financial Report (JOI21_financial)	C++17	100 / 100	644 ms	20452 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9 + 8;

int n, D, a[MAX_N];

struct sgt {
	int n;
	vector<int> mx;
	sgt(int _n) : n(_n) {
		mx.resize(n<<1, -inf);
	}
	void modify(int i, int v) {
		i += n;
		mx[i] = v;
		while (i>>=1) {
			mx[i] = max(mx[i<<1], mx[i<<1|1]);
		}
	}
	int qry(int l, int r) {
		l += n, r += n;
		int res = -inf;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmax(res, mx[l++]);
			if (r&1) chmax(res, mx[--r]);
		}
		return res;
	}
};

int solve() {
	vector<int> id(n); iota(AI(id), 0);
	vector<int> dp(n, -inf);

	sort(AI(id), [&](int i, int j) {
		return make_pair(a[i], -i) < make_pair(a[j], -j);
	});

	sgt tree(n);

	set<int> alive, bad;

	bad.insert(-1);
	auto check = [&](int id) {
		if (id < 0) return;
		bool is_bad = false;
		auto it = alive.upper_bound(id);
		if (it == end(alive) || *it - id > D)
			is_bad = true;
		if (is_bad) bad.insert(id);
		else bad.erase(id);
	};
	auto add_in = [&](int id) {
		auto it = alive.insert(id).first;
		if (it != begin(alive))
			check(*prev(it));
		check(id);
	};
	for (int i : id) {

		add_in(i);

		dp[i] = 1;

		int l = *prev(bad.lower_bound(i)) + 1, r = i;

		DE(l, r, i, tree.qry(l, r));

		chmax(dp[i], tree.qry(l, r) + 1);

		tree.modify(i, dp[i]);
	}

	return *max_element(AI(dp));
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> D;
	for (int i = 0;i < n;++i)
		cin >> a[i];


	int res = solve();

	cout << res << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int solve()':
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Main.cpp:82:3: note: in expansion of macro 'DE'
   82 |   DE(l, r, i, tree.qry(l, r));
      |   ^~

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