Submission #726975

#	Time	Username	Problem	Language	Result	Execution time	Memory
726975		dozer	Misspelling (JOI22_misspelling)	C++14	57 / 100	362 ms	155724 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 500005
#define A 30
#define int long long


const int modulo = 1e9 + 7;

vector<int> del[2][N];
int range[2][N];
int dp[N][A], pre[N][A], suf[N][A], v[2][N];


int add(int a, int b)
{
	if (a + b < modulo) return a + b;
	return a + b - modulo;
}

int mul(int a, int b)
{
	return (a * b) % modulo;
}


int subs(int a, int b)
{
	if (a < b) return a - b + modulo;
	return a - b;
}

int fe(int a, int b)
{
	if (b == 0) return 1;
	if (b % 2) return mul(a, fe(a, b - 1));
	int tmp = fe(a, b / 2);
	return mul(tmp, tmp);
}


int32_t main()
{
	fastio();


	int n, m;
	cin>>n>>m;
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		cin>>a>>b;
		if (a > b) range[1][b + 1] = max(range[1][b + 1], a);
		else range[0][a + 1] = max(range[0][a + 1], b);
	}

	set<int> undone[2];
	vector<int> pre(A, 0), suf(A, 0);

	for (int i = n; i >= 1; i--)
	{
		for (int j = 1; j <= 26; j++)
		{
			dp[i][j] = add(pre[j - 1], suf[j + 1]);
			dp[i][j] = add(dp[i][j], 1);
		}
		for (int j = 0; j < 2; j++)
		{
			if (range[j ^ 1][i] == 0) 
			{
				undone[j].insert(i);
				for (int k = 1; k <= 26; k++)
					v[j][k] = add(v[j][k], dp[i][k]);
			}
			else
			{
				auto it = undone[j].begin();
				while(it != undone[j].end() && *it <= range[j ^ 1][i])
				{
					for (int k = 1; k <= 26; k++)
						v[j][k] = subs(v[j][k], dp[*it][k]);
					it = undone[j].erase(it);
				}
 			}
		}
/*
		cout<<i<<" : ";
		for (auto j : undone[0]) cout<<j<<sp;
		cout<<"| ";
		for (auto j : undone[1]) cout<<j<<sp;
		cout<<endl;
*/
		for (int j = 1; j <= 26; j++)
			pre[j] = add(pre[j - 1], v[1][j]);
		for (int j = 26; j >= 1; j--)
			suf[j] = add(suf[j + 1], v[0][j]);


	}


	int ans = 0;
	for (int i = 0; i < 2; i++)
	{
		for (auto j : undone[i])
		{
			if (j == 1) continue;
			for (int k = 1; k <= 26; k++)
			{
				if (i == 0) ans = add(ans, mul(k - 1, dp[j][k]));
				else ans = add(ans, mul(26 - k, dp[j][k]));
			}
		}
	}
	ans = add(ans, 26);

	cout<<ans<<endl;


	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
} 

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