Submission #1226461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226461		chaeryeong	Arcade (NOI20_arcade)	C++20	100 / 100	188 ms	11672 KiB

Arcade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
t[j] - t[i] >= abs(a[i] - a[j])
t[j] - t[i] >= a[i] - a[j] and t[j] - t[i] >= a[j] - a[i]


t[j] + a[j] >= t[i] + a[i] and t[j] - a[j] >= t[i] - a[i]
*/
const int M = 5e5 + 25;
int n, m;
array <ll, 2> a[M];
int vis[M];
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i][0];
	}
	for (int i = 1; i <= m; i++) {
		cin >> a[i][1];
	}
	sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; i++) {
		a[i] = {a[i][0] - a[i][1], a[i][0] + a[i][1]};
	}
	sort(a + 1, a + m + 1);
	vector <int> c;
	for (int i = 1; i <= m; i++) {
		c.push_back(a[i][1]);
	}
	set <int> ee;
	for (auto i : c) {
		auto g = ee.lower_bound(i + 1);
		if (g == ee.begin()) {
			ee.insert(i);
		} else {
			g--;
			ee.erase(g);
			ee.insert(i);
		}
	}
	cout << (int)ee.size() << '\n';
}	
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15