Submission #544673

#	Time	Username	Problem	Language	Result	Execution time	Memory
544673		blue	Misspelling (JOI22_misspelling)	C++17	60 / 100	4105 ms	333820 KiB

misspelling

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

const ll mod = 1'000'000'007LL;

ll ad(ll a, ll b)
{
	return (a+b)%mod;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	vi lrg(1+N+1, -1); //s[i] > s[i+1]
	vi sml(1+N+1, -1); //s[i] < s[i+1]

	int C = 26;

	for(int j = 1; j <= M; j++)
	{
		int A, B;
		cin >> A >> B;

		if(A < B) lrg[A] = max(lrg[A], B-1);
		if(A > B) sml[B] = max(sml[B], A-1);
	}

	vi lrglim(1+N+1, -1), smllim(1+N+1, -1);
	//the largest index i <= j-1 such that lrg[i] >= j-1



	// cerr << "\n\n\n";
	// cerr << "computing large\n";





	// for(int j = N+1; j >= 1; j--)
	// 	for(int i = 1; i <= j-1; i++)
	// 		if(lrg[i] >= j-1)
	// 			lrglim[j] = max(lrglim[j], i);
	// for(int i = 1; i <= N+1; i++) cerr << lrglim[i] << ' ';
	// 	cerr << '\n';

	// cerr << lrg[3] << '\n';


	set<int> currlarge;

	vi largelist[1+N+1];
	for(int i = 1; i <= N; i++)
	{
		if(lrg[i] == -1) continue;
		largelist[lrg[i]].push_back(i);
	}

	for(int i = N+1; i >= 1; i--)
	{

		for(int z : largelist[i-1])
		{
			// cerr << "inserting " << z << '\n';
			currlarge.insert(z);
		}

		auto f = currlarge.lower_bound(i);
		if(f == currlarge.begin()) continue;
		f--;
		lrglim[i] = *f;

		// cerr << "lrglim " << i << " = " << lrglim[i] << '\n';
	}

	// for(int i = 1; i <= N+1; i++) cerr << lrglim[i] << ' ';
	// 	cerr << '\n';











	set<int> currsmall;

	vi smalllist[1+N+1];
	for(int i = 1; i <= N; i++)
	{
		if(sml[i] == -1) continue;
		smalllist[sml[i]].push_back(i);
	}

	for(int i = N+1; i >= 1; i--)
	{

		for(int z : smalllist[i-1])
		{
			// cerr << "inserting " << z << '\n';
			currsmall.insert(z);
		}

		auto f = currsmall.lower_bound(i);
		if(f == currsmall.begin()) continue;
		f--;
		smllim[i] = *f;

		// cerr << "lrglim " << i << " = " << lrglim[i] << '\n';
	}













	vvll delta(1+N+1, vll(1+C+1, 0));


	vvll DP(1+N+1, vll(1+C+1, 0));
	DP[N+1][C+1] = 1;

	ll tot = 0;


	// for(int i = 1; i <= N; i++) cerr << lrglim[i] << ' ';
	// 	cerr << '\n';


	// cerr << "original\n";

	// for(int i = N; i >= 1; i--)
	// {
	// 	int maxlrg = -1, maxsml = -1;
	// 	for(int j = i+1; j <= N+1; j++)
	// 	{
	// 		maxlrg = max(maxlrg, lrg[j-1]);
	// 		maxsml = max(maxsml, sml[j-1]);

	// 		for(int ci = 1; ci <= C; ci++)
	// 		{
	// 			for(int cj = 1; cj <= C+1; cj++)
	// 			{
	// 				if(ci == cj) continue;

	// 				// if(j-1 <= maxlrg && ci < cj) continue;
	// 				if(ci < cj && i <= lrglim[j]) continue;

	// 				// if(j-1 <= maxsml && ci > cj) continue;
	// 				if(ci > cj && i <= smllim[j]) continue;

	// 				// if(ci == 1 && cj == 26) cerr << "good large pair " << i << ' ' << j << '\n';

	// 				// cerr << i << ' ' << j << ' ' << ci << ' ' << cj << '\n';

	// 				DP[i][ci] = ad(DP[i][ci], DP[j][cj]);
	// 			}
	// 		}
	// 	}

	// 	for(int ci = 1; ci <= C+1; ci++)
	// 		cerr << i << ' ' << ci << " : " << DP[i][ci] << '\n';
	// }






	delta[N][C+1] = -1;

	for(int j = N+1; j >= 1; j--)
	{
		if(j <= N)
		{
			for(int cj = 1; cj <= C+1; cj++)
			{
				DP[j][cj] = ad(DP[j+1][cj], delta[j][cj]);
				// DP[j][cj] = 
			}
		}

		for(int cj = 1; cj <= C+1; cj++)
		{
			for(int ci = 1; ci <= C; ci++)
			{
				if(ci == cj) continue;

				if(ci < cj)
				{
					delta[j-1][ci] = ad(delta[j-1][ci], DP[j][cj]);
					if(lrglim[j] >= 0)
						delta[lrglim[j]][ci] = ad(delta[lrglim[j]][ci], mod - DP[j][cj]);
				}
				else
				{
					delta[j-1][ci] = ad(delta[j-1][ci], DP[j][cj]);
					if(smllim[j] >= 0)
						delta[smllim[j]][ci] = ad(delta[smllim[j]][ci], mod - DP[j][cj]);
				}
			}
		}

		// for(int cj = 1; cj <= C+1; cj++)
		// 	cerr << j << ' ' << cj << " : " << DP[j][cj] << '\n';
	}

















	for(int ci = 1; ci <= C; ci++)
	{
		tot = ad(tot, DP[1][ci]);
		// cerr << ci << " : " << DP[1][ci] << '\n';
	}

	cout << tot << '\n';
}

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