Submission #572018

#	Time	Username	Problem	Language	Result	Execution time	Memory
572018		pnm1384	Misspelling (JOI22_misspelling)	C++14	29 / 100	848 ms	132084 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int mod = 1e9 + 7;

#define F first
#define S second

const int N = 5e5 + 20, LG = 28;
vector<int> vtl[N], vtr[N];
int ps[N][LG];
pair<int, int> a[N];
set<pair<int, int>> st[2];

inline void mkey(int& x)
{
	while (x >= mod) x -= mod;
	while (x < 0) x += mod;
	return;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		x--; y--;
		swap(x, y);
		a[i] = {x, y};
		vtl[min(x, y)].push_back(i);
		vtr[max(x, y)].push_back(i);
	}
	for (int i = 0; i < 26; i++) ps[1][i + 1] = i + 1;
	for (int ind : vtl[0])
	{
		if (a[ind].F == 0) st[0].insert({0, ind});
		else st[1].insert({0, ind});
	}
	for (int i = 1; i < n; i++)
	{
		int mx0 = -1, mx1 = -1;
		if (!st[0].empty())
		{
			auto it = st[0].end();
			it--;
			mx0 = it->F;
		}
		if (!st[1].empty())
		{
			auto it = st[1].end();
			it--;
			mx1 = it->F;
		}
		for (int ch = 0; ch < 26; ch++)
		{
			int mx = max(mx1, mx0);
			int ans = 0;
			mkey(ans += ps[i][26] - ps[mx + 1][26]);
			int bb = 0;
			mkey(bb = ps[i][ch + 1] - ps[i][ch]);
			mkey(bb -= ps[mx + 1][ch + 1] - ps[mx + 1][ch]);
			mkey(ans -= bb);
			ps[i + 1][ch + 1] = ans;
			if (mx0 >= mx1)
			{
				mkey(ps[i + 1][ch + 1] += ps[mx0 + 1][ch] - ps[mx1 + 1][ch]);
			}
			else
			{
				int bb = 0;
				mkey(bb = ps[mx1 + 1][26] - ps[mx1 + 1][ch + 1]);
		//		cout << "     " << bb << '\n';
				mkey(bb -= ps[mx0 + 1][26] - ps[mx0 + 1][ch + 1]);
				mkey(ps[i + 1][ch + 1] += bb);
			}
		//	cout << "      " << i + 1 << "  " << ch << "   " << ps[i + 1][ch + 1] << '\n';
			mkey(ps[i + 1][ch + 1] += ps[i + 1][ch]);
			mkey(ps[i + 1][ch + 1] += ps[i][ch + 1]);
			mkey(ps[i + 1][ch + 1] -= ps[i][ch]);
		//	cout << "      " << i + 1 << "  " << ch << " " << ps[i + 1][ch + 1] << '\n';
		}
		for (int ind : vtl[i])
		{
			if (a[ind].F == i) st[0].insert({i, ind});
			else st[1].insert({i, ind});
		}
		for (int ind : vtr[i])
		{
			if (a[ind].S == i) st[0].erase({a[ind].F, ind});
			else st[1].erase({a[ind].F, ind});
		}
	}
	cout << ps[n][26];
	return 0;
}

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