Submission #1303930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303930		yonatanl	Arcade (NOI20_arcade)	C++20	0 / 100	1 ms	584 KiB

Arcade

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

void solve() {
	ll n, m;
	cin >> n >> m;
	vpll arr(m);
	rep(i, 0, m) cin >> arr[i].second;
	rep(i, 0, m) cin >> arr[i].first;
	sort(arr.begin(), arr.end());
	vll dp(m);
	dp[0] = 1;
	ll l = 0;
	multiset<pll> s;
	s.insert({ arr[0].second, arr[0].first });
	rep(i, 1, m) {
		pll cur = { arr[i].second, arr[i].first };
		s.insert(cur);
		/*cout << "s: " << '\n';
		for (auto& it : s) {
			cout << it.first << ' ' << it.second << '\n';
		}*/
		while (!s.empty()){
			bool updated = false;
			if (*(--s.end()) != cur) {
				auto itR = ++(s.find(cur));
				ll a1 = arr[i].first;
				ll a2 = (*itR).second;
				ll t1 = arr[i].second;
				ll t2 = (*itR).first;
				if (abs(a1 - a2) > t2 - t1) {
					// Won't make it in time
					s.erase({ arr[l].second, arr[l].first });
					l++;
					updated = true;
				}
			}
			if (!s.empty() && *s.begin() != cur) {
				auto itL = --(s.find(cur));
				ll a1 = arr[i].first;
				ll a2 = (*itL).second;
				ll t1 = arr[i].second;
				ll t2 = (*itL).first;
				if ((abs(a1 - a2) > t1 - t2) && !updated) {
					// Won't make it in time
					s.erase({ arr[l].second, arr[l].first });
					l++;
					updated = true;
				}
			}
			if (!updated) break;
		}
		if (l > 0) dp[i] = dp[l - 1] + 1;
		else dp[i] = 1;
	}
	/*cout << "dp: ";
	rep(i, 0, m) cout << dp[i] << ' ';
	cout << '\n';*/
	cout << dp[m - 1] << '\n';
}

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

	solve();
}

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