oj.uz

Submission #420284

# Submission time Handle Problem Language Result Execution time Memory
420284 2021-06-08T08:55:30 Z IOrtroiii Financial Report (JOI21_financial) C++14
5 / 100
 1081 ms 34676 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int N, D; cin >> N >> D;
	vector<int> A(N); for (int &a : A) cin >> a;
	
	vector<int> ord(N); iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](const int &i, const int &j) { 
		return make_pair(A[i], -i) < make_pair(A[j], -j); 
	});
	int S = 1;
	while (S < N) S *= 2;
	vector<int> loc(N);
	for (int i = 0; i < N; ++i) loc[ord[i]] = i;

	struct Node {
		int best = 0;
		int pref = 0;
		int suff = 0;
		bool all = false;
	};

	auto merge = [&](Node l, Node r) {
		Node ans;
		ans.all = l.all & r.all;
		ans.best = max({l.best, r.best, l.suff + r.suff});
		ans.pref = l.all ? l.pref + r.pref : l.pref;
		ans.suff = r.all ? r.suff + l.suff : r.suff;
		return ans;
	};

	vector<Node> tree0(2 * S);
	auto modify0 = [&](int p) {
		tree0[p += S] = {1, 1, 1, true};
		p /= 2;
		while (p > 0) {
			tree0[p] = merge(tree0[2 * p], tree0[2 * p + 1]);
			p /= 2;
		}	
	};

	auto query0 = [&](int l, int r) {
		Node ansl{};
		Node ansr{};
		for (l += S, r += S; l <= r; l /= 2, r /= 2) {
			if (l % 2) ansl = merge(ansl, tree0[l++]);
			if (r % 2 == 0) ansr = merge(tree0[r--], ansr);
		}
		return merge(ansl, ansr).best;
	};

	vector<vector<int>> evts(N);
	reverse(ord.begin(), ord.end());
	for (int i : ord) {
		int lo = i, hi = N - 1;
		while (lo < hi) {
			int mi = (lo + hi + 1) / 2;
			if (query0(i, mi) <= D) lo = mi;
			else hi = mi - 1;
		}
		if (lo + 1 < N) {
			evts[lo + 1].push_back(i);
		}
		modify0(i);
	}

	vector<int> tree1(2 * S);
	auto modify1 = [&](int p, int v) {
		tree1[p += S] = v;
		p /= 2;
		while (p > 0) {
			tree1[p] = max(tree1[2 * p], tree1[2 * p + 1]);
			p /= 2;
		}
	};
	auto query1 = [&](int l, int r) {
		int ans = 0;
		for (l += S, r += S; l <= r; l /= 2, r /= 2) {
			if (l % 2) ans = max(ans, tree1[l++]);
			if (r % 2 == 0) ans = max(ans, tree1[r--]);
		}
		return ans;
	};

	int ans = 0;
	for (int i = 0; i < N; ++i) {
		for (int j : evts[i]) {
			modify1(loc[j], 0);
		}
		int dp = query1(0, loc[i]) + 1;
		ans = max(ans, dp);
		modify1(loc[i], dp);
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 31396 KB Output is correct
2 Correct 663 ms 34076 KB Output is correct
3 Incorrect 903 ms 34676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 31388 KB Output is correct
2 Correct 932 ms 31512 KB Output is correct
3 Correct 1081 ms 31392 KB Output is correct
4 Correct 1031 ms 31424 KB Output is correct
5 Correct 950 ms 31392 KB Output is correct
6 Correct 1058 ms 31512 KB Output is correct
7 Correct 687 ms 31396 KB Output is correct
8 Correct 690 ms 31512 KB Output is correct
9 Correct 713 ms 31332 KB Output is correct
10 Correct 917 ms 31428 KB Output is correct
11 Correct 1042 ms 31388 KB Output is correct
12 Correct 960 ms 31396 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -