test/ABC179-F.test.cpp

View this file on GitHub
Last update: 2023-03-10 16:43:07+09:00
Problem: https://atcoder.jp/contests/abc179/tasks/abc179_f

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc179/tasks/abc179_f"

#include "../src/utility/monoid/minMonoid.hpp"
#include "../src/dataStructure/dualSegmentTree.hpp"

#include <iostream>
#include <vector>

using seg = zawa::dualSegmentTree<zawa::minMonoid<int>>;

int main() {
	int N, Q; std::cin >> N >> Q;
	seg R(std::vector(N - 1, N - 1)), C(std::vector(N - 1, N - 1));
	long long ans = (long long)(N - 2) * (N - 2);
	for (int _ = 0 ; _ < Q ; _++) {
		int T, X; std::cin >> T >> X;
		X -= 2;
		if (T == 1) {
			ans -= C[X] - 1;
			R.update(0, C[X], X + 1);
		}
		else {
			ans -= R[X] - 1;
			C.update(0, R[X], X + 1);
		}
	}
	std::cout << ans << std::endl;
}

#line 1 "test/ABC179-F.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc179/tasks/abc179_f"

#line 2 "src/utility/monoid/minMonoid.hpp"

#include <algorithm>
#include <limits>

namespace zawa {

template <class T>
struct minMonoid {
	using valueType = T;
	static constexpr valueType identity = std::numeric_limits<valueType>::max();
	static valueType operation(const valueType& a, const valueType& b) {
		return std::min(a, b);
	}
};

};
#line 2 "src/dataStructure/dualSegmentTree.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <class monoid>
class dualSegmentTree {
private:
	using O = typename monoid::valueType;
	int N;
	std::vector<O> dat;

	constexpr int left(int v) const {
		return v << 1;
	}

	constexpr int right(int v) const {
		return v << 1 | 1;
	}

	constexpr int parent(int v) const {
		return v >> 1;
	}

	inline void propagate(int v) {
		if (left(v) < (int)dat.size()) {
			dat[left(v)] = monoid::operation(dat[left(v)], dat[v]);
		}
		if (right(v) < (int)dat.size()) {
			dat[right(v)] = monoid::operation(dat[right(v)], dat[v]);
		}
		dat[v] = monoid::identity;
	}

	void push(int v) {
		int height = 31 - __builtin_clz(v);
		for (int i = height ; i >= 1 ; i--) {
			propagate(v >> i);
		}
	}

public:
	dualSegmentTree() {}
	dualSegmentTree(int _N) : N(_N), dat(_N << 1, monoid::identity) {}
	dualSegmentTree(const std::vector<O>& A) : N((int)A.size()), dat(A.size() << 1, monoid::identity) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			dat[i + N] = A[i];
		}
	}

	O operator[](int i) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		return dat[i];
	}

	void set(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = value;
	}

	void update(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = monoid::operation(dat[i], value);
	}

	void update(int l, int r, const O& value) {
		assert(0 <= l and l < N);
		assert(l <= r and r <= N);
		if (l == r) {
			return;
		}
		l += N; r += N;
		push(l); push(r - 1);
		for ( ; l < r ; l = parent(l), r = parent(r)) {
			if (l & 1) {
				dat[l] = monoid::operation(dat[l], value);
				l++;
			}
			if (r & 1) {
				r--;
				dat[r] = monoid::operation(dat[r], value);
			}
		}
	}

	inline std::vector<O> _dat() const {
		return dat;
	}
};

} // namespace 
#line 5 "test/ABC179-F.test.cpp"

#include <iostream>
#line 8 "test/ABC179-F.test.cpp"

using seg = zawa::dualSegmentTree<zawa::minMonoid<int>>;

int main() {
	int N, Q; std::cin >> N >> Q;
	seg R(std::vector(N - 1, N - 1)), C(std::vector(N - 1, N - 1));
	long long ans = (long long)(N - 2) * (N - 2);
	for (int _ = 0 ; _ < Q ; _++) {
		int T, X; std::cin >> T >> X;
		X -= 2;
		if (T == 1) {
			ans -= C[X] - 1;
			R.update(0, C[X], X + 1);
		}
		else {
			ans -= R[X] - 1;
			C.update(0, R[X], X + 1);
		}
	}
	std::cout << ans << std::endl;
}