Submission #552248

#	Time	Username	Problem	Language	Result	Execution time	Memory
552248		LucaDantas	Misspelling (JOI22_misspelling)	C++17	60 / 100	2921 ms	6240 KiB

misspelling

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 20010, mod = 1e9+7;

int edge[maxn][2];

int dp[maxn][26]; // dp[pos][cor(grp(pos))]

inline int sum(int a, int b) { a += b; if(a >= mod) a -= mod; return a; }
inline int sub(int a, int b) { a -= b; if(a < 0) a += mod; return a; }
inline void add(int& a, int b) { a += b; if(a >= mod) a -= mod; }


int main() {
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int a, b, t = 0;
		scanf("%d %d", &a, &b);
		if(a > b)
			swap(a, b), t = 1;
		// t: 0 => color[group(a)] <= color[min(b, group(a)+1)], 1 => color[group(a)] >= color[min(b, group(a)+1)]
		edge[a][t] = max(edge[a][t], b);
	}
	
	for(int cor = 0; cor < 26; cor++)
		dp[1][cor] = 1;

	int ans = 0;
	for(int i = 1; i <= n; i++) {
		int itv[2]{};
		itv[0] = edge[i][0], itv[1] = edge[i][1];

		int pref[26]{}, suf[26]{};
		pref[0] = dp[i][0], suf[25] = dp[i][25];

		for(int cor = 1; cor < 26; cor++)
			pref[cor] = sum(pref[cor-1], dp[i][cor]);
		for(int cor = 24; cor >= 0; cor--)
			suf[cor] = sum(suf[cor+1], dp[i][cor]);
		int tot = suf[0]; // só pra ficar mais legível depois
		// printf("%d == %d\n", i, tot);

		for(int j = i; j < n; j++) {
			for(int flag : {0, 1})
				itv[flag] = max(itv[flag], edge[j][flag]);

			// printf("%d %d | %d %d\n", i, j, itv[0], itv[1]);
			
			if(itv[0] > j && itv[1] > j)
				continue;
			
			if(itv[0] > j) // cor[grp[i]] <= cor[grp[j]]
				for(int cor = 1; cor < 26; cor++)
					add(dp[j+1][cor], pref[cor-1]);
			
			if(itv[1] > j) // cor[grp[i]] >= cor[grp[j]]
				for(int cor = 24; cor >= 0; cor--)
					add(dp[j+1][cor], suf[cor+1]);

			if(itv[0] <= j && itv[1] <= j) // eles só não podem ser da mesma cor senao taria recontando
				for(int cor = 0; cor < 26; cor++)
					add(dp[j+1][cor], sub(tot, dp[i][cor]));
		}

		add(ans, tot);
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

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

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