Submission #586940

#	Time	Username	Problem	Language	Result	Execution time	Memory
586940		dutinmeow	Misspelling (JOI22_misspelling)	C++17	100 / 100	2555 ms	492568 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

const int $S = 26, MOD = 1e9 + 7;

struct mint {
	int v;

	mint() : v(0) {}

	mint(int _v) : v(_v % MOD) {}

	mint &operator+=(const mint &rhs) { 
		v += rhs.v; 
		if (v >= MOD)
			v -= MOD;
		return *this;
	}

	mint &operator-=(const mint &rhs) { 
		v -= rhs.v; 
		if (v < 0)
			v += MOD;
		return *this;
	}
};

mint operator+(mint lhs, const mint &rhs) { return lhs += rhs; }

mint operator-(mint lhs, const mint &rhs) { return lhs -= rhs; }

ostream &operator<<(ostream &os, const mint &m) { return os << m.v; }

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> E(N);
	vector<tuple<int, int, int>> A(M);	
	for (int i = 0; i < M; i++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		if (l == r)
			continue;
		else if (l < r) 
			A[i] = {l + 1, r, -1};
		else if (l > r)
			A[i] = {r + 1, l, 1};
		E[min(l, r)].push_back(i);
	}

	// dbg(A, E)

	using st_node = array<mint, $S>;
	vector<st_node> st_tree1(4 * N), st_tree2(4 * N);
	vector<bool> st_lazy1(4 * N, false), st_lazy2(4 * N, false);

	for_each(st_tree1.begin(), st_tree1.end(), [](st_node &n) { n.fill(0); });
	for_each(st_tree2.begin(), st_tree2.end(), [](st_node &n) { n.fill(0); });

	auto st_update = y_combinator([&](auto st_update, int i, const st_node &v, int t, int tl, int tr, vector<st_node> &st_tree, vector<bool> &st_lazy) -> void {
		if (tl == tr) {
			assert(tl == i);
			st_tree[t] = v;
			return;
		}
		if (st_lazy[t]) {
			st_tree[t * 2].fill(0);
			st_tree[t * 2 + 1].fill(0);
			st_lazy[t * 2] = st_lazy[t * 2 + 1] = true;
			st_lazy[t] = false;
		}
		int tm = (tl + tr) / 2;
		if (i <= tm)
			st_update(i, v, t * 2, tl, tm, st_tree, st_lazy);
		else 
			st_update(i, v, t * 2 + 1, tm + 1, tr, st_tree, st_lazy);
		for (int c = 0; c < $S; c++)
			st_tree[t][c] = st_tree[t * 2][c] + st_tree[t * 2 + 1][c];
	});	

	auto st_clear = y_combinator([&](auto st_clear, int l, int r, int t, int tl, int tr, vector<st_node> &st_tree, vector<bool> &st_lazy) -> void {
		if (r < tl || tr < l || st_lazy[t])
			return;
		if (l <= tl && tr <= r) {
			st_tree[t].fill(0);
			st_lazy[t] = true;
			return;
		}
		int tm = (tl + tr) / 2;
		st_clear(l, r, t * 2, tl, tm, st_tree, st_lazy);
		st_clear(l, r, t * 2 + 1, tm + 1, tr, st_tree, st_lazy);
		for (int c = 0; c < $S; c++)
			st_tree[t][c] = st_tree[t * 2][c] + st_tree[t * 2 + 1][c];
	});

	vector<st_node> dp(N);
	for (int i = N - 1; i >= 0; i--) {
		if (i == N - 1) {
			dp[i].fill(1);
		} else {
			for (int k : E[i]) {
				auto [l, r, p] = A[k];
				if (p == 1)
					st_clear(l, r, 1, 0, N - 1, st_tree1, st_lazy1);
				else if (p == -1)
					st_clear(l, r, 1, 0, N - 1, st_tree2, st_lazy2);
			}
			for (int c = 0; c < $S; c++) {
				dp[i][c] = 1;
				for (int d = 0; d < c; d++)
					dp[i][c] += st_tree1[1][d];
				for (int d = c + 1; d < $S; d++)
					dp[i][c] += st_tree2[1][d];
			}
		}
		st_update(i, dp[i], 1, 0, N - 1, st_tree1, st_lazy1);
		st_update(i, dp[i], 1, 0, N - 1, st_tree2, st_lazy2);
	}

	mint ans = 0;
	for (int c = 0; c < $S; c++)
		ans += dp[0][c];
	cout << ans << '\n';
}

Compilation message (stderr)

misspelling.cpp:4: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    4 | #pragma region y_combinator
      | 
misspelling.cpp:29: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   29 | #pragma endregion y_combinator
      |

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11