Submission #547412

#	Time	Username	Problem	Language	Result	Execution time	Memory
547412		skittles1412	Misspelling (JOI22_misspelling)	C++17	100 / 100	586 ms	503064 KiB

misspelling

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const long mod = 1e9 + 7;

struct DS {
	long ans = 0;
	vector<pair<int, long>> v;

	DS() {}

	void set(int ind, long x) {
		v.emplace_back(ind, x);
		ans += x;
		if (ans >= mod) {
			ans -= mod;
		}
	}

	void clear(int ind) {
		while (sz(v) && v.back().first <= ind) {
			ans -= v.back().second;
			if (ans < 0) {
				ans += mod;
			}
			v.pop_back();
		}
	}

	long query() const {
		return ans;
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, bool>> arr[n];
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		bool lt = r < l;
		if (l > r) {
			swap(l, r);
		}
		arr[l].emplace_back(r, lt);
	}
	long dp[n][26] {};
	DS psumlt[26], psumgt[26];
	for (int i = n - 1; i >= 0; i--) {
		for (auto& [x, lt] : arr[i]) {
			if (lt) {
				for (auto& a : psumlt) {
					a.clear(x);
				}
			} else {
				for (auto& a : psumgt) {
					a.clear(x);
				}
			}
		}
		for (int j = 0; j < 26; j++) {
			dp[i][j] = (1 + psumlt[j].query() + psumgt[j].query()) % mod;
		}
		{
			long psum = 0;
			for (int j = 0; j < 26; j++) {
				psumlt[j].set(i, psum);
				psum += dp[i][j];
				if (psum >= mod) {
					psum -= mod;
				}
			}
		}
		{
			long psum = 0;
			for (int j = 26 - 1; j >= 0; j--) {
				psumgt[j].set(i, psum);
				psum += dp[i][j];
				if (psum >= mod) {
					psum -= mod;
				}
			}
		}
	}
	long ans = 0;
	for (auto& a : dp[0]) {
		ans += a;
	}
	ans %= mod;
	cout << ans << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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