oj.uz

Submission #1105635

# Submission time Handle Problem Language Result Execution time Memory
1105635 2024-10-27T07:04:20 Z SamNguyen Arcade (NOI20_arcade) C++14
0 / 100
 5 ms 18768 KB 
#include <bits/stdc++.h>
using namespace std;

template <int N>
class BIT {
private:
	int n, bit[N];

public:
	void init(int _n) {
		n = _n;
		fill(bit, bit + n + 1, 0);
	}

	inline void update(int i, int v) {
		for (; i <= n; i += i & -i)
			bit[i] = max(bit[i], v);
	}

	inline int get(int i) {
		int res = 0;
		for (; i > 0; i -= i & -i)
			res = max(res, bit[i]);
		return res;
	}
};

const int MAX = 5e5 + 7;
int D, N, T[MAX], A[MAX];
pair<int, int> coord[MAX];
vector<int> ys_by_x[MAX];

void input() {
	cin >> D >> N;
	for (int i = 1; i <= N; i++)
		cin >> T[i];
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	vector<int> Xs, Ys;
	for (int i = 1; i <= N; i++) {
		int x = A[i] + T[i], y = A[i] - T[i];
		Xs.push_back(x);
		Ys.push_back(y);
		coord[i] = make_pair(x, y);
	}

	sort(Xs.begin(), Xs.end());
	sort(Ys.begin(), Ys.end());
	Xs.resize(unique(Xs.begin(), Xs.end()) - Xs.begin());
	Ys.resize(unique(Ys.begin(), Ys.end()) - Ys.begin());

	for (int i = 1; i <= N; i++) {
		int x, y;
		tie(x, y) = coord[i];
		x = lower_bound(Xs.begin(), Xs.end(), x) - Xs.begin() + 1;
		y = lower_bound(Ys.begin(), Ys.end(), y) - Ys.begin() + 1;

		coord[i] = make_pair(x, y);
		ys_by_x[x].push_back(y);
	}
}

// min chain = max path
BIT<MAX> bit;

void solve() {
	bit.init(N);
	for (int x = N; x >= 1; x--) {
		vector<int> new_vals;

		for (int y : ys_by_x[x])
			new_vals.push_back(bit.get(y - 1) + 1);

		auto it = new_vals.begin();
		for (int y : ys_by_x[x]) 
			bit.update(y, *(it++));
	}

	int ans = bit.get(N);
	cout << ans;
}
	
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -