test/ImosLinear.test.cpp

• View this file on GitHub
• Last update: 2021-04-06 14:24:56+09:00
• Problem: https://yukicoder.me/problems/no/1008

Depends on

• DataStructure/ImosLinear.cpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1008"
#include "./../DataStructure/ImosLinear.cpp"
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	using ll = long long;

	int n, m;
	cin >> n >> m;
	vector<ll> a(n);
	for (ll& i : a) {
		cin >> i;
	}
	vector<pair<int, ll>> xw(m);
	for (auto& [x, w] : xw) {
		cin >> x >> w;
		x--;
	}

	auto check = [&](ll c) {
		ImosLinear<ll> imos(n);
		for (auto [x, w] : xw) {
			imos.add(x, x + 1, w, 0);
			int left = min<ll>(x, w / c);
			imos.add(x - left, x, w - c * left, c);
			int right = min<ll>(n - 1 - x, w / c);
			imos.add(x + 1, x + 1 + right, w - c, -c);
		}
		imos.build();
		for (int i = 0; i < n; ++i) {
			if (imos[i] >= a[i]) {
				return false;
			}
		}
		return true;
	};

	ll sum_w = 0, min_a = 10000000000;
	for (ll i : a) {
		min_a = min(min_a, i);
	}
	for (auto [x, w] : xw) {
		sum_w += w;
	}

	if (sum_w < min_a) {
		cout << 0 << '\n';
	} else if (!check(1000000099)) {
		cout << -1 << '\n';
	} else {
		ll ng = 0, ok = 1000000099;
		while (ok - ng > 1) {
			ll mid = (ok + ng) / 2;
			(check(mid) ? ok : ng) = mid;
		}
		cout << ok << '\n';
	}
}

#line 1 "test/ImosLinear.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1008"
#line 2 "DataStructure/ImosLinear.cpp"
#include <vector>
#include <algorithm>
#include <cassert>

template <class T> class ImosLinear {
public:
	using value_type = T;
	using data_type = std::vector<value_type>;

private:
	std::size_t n;
	data_type X, A, B;
	bool builded = false;

public:
	ImosLinear(std::size_t _n) : n(_n), X(_n), A(_n + 1), B(_n + 1) {}
	void add(std::size_t l, std::size_t r, value_type a,
	         value_type b) {  // [l, r) += a + (i - l) * b
		if (l >= r) return;
		assert(!builded);
		l = std::min(l, n);
		r = std::min(r, n);
		A[l] += a - b * l;
		B[l] += b;
		A[r] -= a - b * l;
		B[r] -= b;
	}
	void build() {
		builded = true;
		for (std::size_t i = 0; i < n; ++i) {
			X[i] = A[i] + B[i] * i;
			A[i + 1] += A[i];
			B[i + 1] += B[i];
		}
	}
	value_type operator[](std::size_t i) const {
		assert(builded);
		return X[i];
	}
	const data_type& to_a() const {
		assert(builded);
		return X;
	}
};
#line 3 "test/ImosLinear.test.cpp"
#include <iostream>
#line 5 "test/ImosLinear.test.cpp"
#include <utility>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	using ll = long long;

	int n, m;
	cin >> n >> m;
	vector<ll> a(n);
	for (ll& i : a) {
		cin >> i;
	}
	vector<pair<int, ll>> xw(m);
	for (auto& [x, w] : xw) {
		cin >> x >> w;
		x--;
	}

	auto check = [&](ll c) {
		ImosLinear<ll> imos(n);
		for (auto [x, w] : xw) {
			imos.add(x, x + 1, w, 0);
			int left = min<ll>(x, w / c);
			imos.add(x - left, x, w - c * left, c);
			int right = min<ll>(n - 1 - x, w / c);
			imos.add(x + 1, x + 1 + right, w - c, -c);
		}
		imos.build();
		for (int i = 0; i < n; ++i) {
			if (imos[i] >= a[i]) {
				return false;
			}
		}
		return true;
	};

	ll sum_w = 0, min_a = 10000000000;
	for (ll i : a) {
		min_a = min(min_a, i);
	}
	for (auto [x, w] : xw) {
		sum_w += w;
	}

	if (sum_w < min_a) {
		cout << 0 << '\n';
	} else if (!check(1000000099)) {
		cout << -1 << '\n';
	} else {
		ll ng = 0, ok = 1000000099;
		while (ok - ng > 1) {
			ll mid = (ok + ng) / 2;
			(check(mid) ? ok : ng) = mid;
		}
		cout << ok << '\n';
	}
}

Back to top page