Submission #765018

#	Time	Username	Problem	Language	Result	Execution time	Memory
765018		ymm	Misspelling (JOI22_misspelling)	C++17	60 / 100	1738 ms	14924 KiB

misspelling

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 20'010;
const int alpha = 26;
const int mod = 1e9+7;

ll dp[N][alpha];
ll ps[N][32];
int mxa[N], mxb[N];
int n, m;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (_,0,m) {
		int i, j;
		cin >> i >> j;
		//i=_+1,j=n;
		--i; --j;
		if (i < j)
			mxa[i] = max(mxa[i], j);
		else
			mxb[j] = max(mxb[j], i);
	}
	dp[n][0] = 1;
	Loop (x,0,alpha)
		ps[n][x+1] = 1;
	LoopR (i,0,n) {
		ll ans[32] = {};
		int a = mxa[i], b = mxb[i];
		Loop (j,i+1,n+1) {
			if (j > a && j > b) {
				Loop (x,0,alpha)
					ans[x] += ps[j][alpha];
				goto end;
			} else if (j > b) {
				Loop (x,0,alpha)
					ans[x] += ps[j][alpha] - ps[j][x+1];
			} else if (j > a) {
				Loop (x,0,alpha)
					ans[x] += ps[j][x];
			}
			a = max(a, mxa[j]);
			b = max(b, mxb[j]);
		}
	end:
		Loop (x,0,alpha)
			dp[i][x] = ans[x] % mod;

		Loop (x,0,alpha)
			ps[i][x+1] = ps[i][x] + dp[i][x];
	}
	ll ans = 0;
	Loop (x,0,alpha)
		ans += dp[0][x];
	ans %= mod;
	cout << ans << '\n';
}

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