Submission #547794

#	Time	Username	Problem	Language	Result	Execution time	Memory
547794		nonsensenonsense1	Misspelling (JOI22_misspelling)	C++17	100 / 100	291 ms	57348 KiB

misspelling

#include <cstdio>
#include <utility>
#include <algorithm>

const int md = 1000000007;

inline int add(int a, int b) {
	a += b;
	if (a >= md) a -= md;
	return a;
}
inline int sub(int a, int b) {
	a -= b;
	if (a < 0) a += md;
	return a;
}
inline int mul(int a, int b) {
	return (long long)a * b % md;
}

const int A = 26;
const int N = 500000;
int n, m, d[N][A], sum[2][A];
bool u[2][N];
std::pair<std::pair<int, int>, bool> a[N];
std::vector<int> un[2];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x;
		--y;
		if (x < y) a[i] = std::make_pair(std::make_pair(x, y), 1);
		else a[i] = std::make_pair(std::make_pair(y, x), 0);
	}
	std::sort(a, a + m);
	for (int i = n - 1, j = m - 1; i >= 0; --i) {
		if (i + 1 < n) {
			for (int j = 0; j < A; ++j) 
				for (int k = 0; k < 2; ++k) sum[k][j] = add(sum[k][j], d[i + 1][j]);
			un[0].push_back(i);
			un[1].push_back(i);
		}
		while (j >= 0 && a[j].first.first == i) {
			while (!un[a[j].second].empty() && un[a[j].second].back() < a[j].first.second) {
				for (int k = 0; k < A; ++k) sum[!a[j].second][k] = sub(sum[!a[j].second][k], d[un[a[j].second].back() + 1][k]);
				un[a[j].second].pop_back();
			}
			--j;
		}
		int less = 1;
		for (int x = 0; x < A; ++x) {
			d[i][x] = less;
			less = add(less, sum[1][x]);
		}
		less = 0;
		for (int x = A - 1; x >= 0; --x) {
			d[i][x] = add(d[i][x], less);
			less = add(less, sum[0][x]);
		}
	}
	int ans = 0;
	for (int i = 0; i < A; ++i) ans = add(ans, d[0][i]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
misspelling.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

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