Submission #586939

#	Time	Username	Problem	Language	Result	Execution time	Memory
586939		dutinmeow	Misspelling (JOI22_misspelling)	C++17	100 / 100	3139 ms	509180 KiB

misspelling

#define _GLIBCXX_DEBUG

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

#pragma region debug

#if defined(LOCAL) && !defined(ONLINE_JUDGE)
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = next(v.begin()); i != v.end(); i++)
		os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = next(d.begin()); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
		}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = next(a.begin()); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
 cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define dbg(...)
#endif

#pragma endregion debug

#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';

	// for (int i = N - 1; i >= 0; i--) 
	// 	dbg("_4\n", i, dp[i]);
}

Compilation message (stderr)

misspelling.cpp:6: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
    6 | #pragma region debug
      | 
misspelling.cpp:200: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
  200 | #pragma endregion debug
      | 
misspelling.cpp:202: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
  202 | #pragma region y_combinator
      | 
misspelling.cpp:227: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
  227 | #pragma endregion y_combinator
      |

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