Submission #605610

#	Time	Username	Problem	Language	Result	Execution time	Memory
605610		Red_Inside	Misspelling (JOI22_misspelling)	C++17	60 / 100	4054 ms	334940 KiB

misspelling

//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=5e5+100,LOG=17,mod=1e9+7;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
#define int ll
const int inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int n, m, t[4*maxn][28][3], dp[maxn][28], temp[30];
multiset <int> st[4];
vector <pii> start[maxn], fin[maxn];

void upd(int v, int tl, int tr, int pos, int val, int x, int ty)
{
	if(pos < tl || tr < pos) return;
	if(tl == tr)
	{
		t[v][x][ty] = val;
		return;
	}
	upd(v * 2, tl, (tl + tr) / 2, pos, val, x, ty);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val, x, ty);
	t[v][x][ty] = (t[v * 2][x][ty] + t[v * 2 + 1][x][ty]) % mod;
}

int get(int v, int tl, int tr, int l, int r, int x, int ty)
{
	if(l > tr || r < tl) return 0;
	if(l <= tl && tr <= r) return t[v][x][ty];
	return (get(v * 2, tl, (tl + tr) / 2, l, r, x, ty) + 
	get(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, x, ty)) % mod;
}

main()
{
	IOS
	cin >> n >> m;
	forn(1, i, m)
	{
		int l, r, ty;
		cin >> l >> r;
		if(l < r) ty = 2;
		else ty = 1, swap(l, r);
		start[l].pb({r, ty});
		fin[r].pb({l, ty});
	}
	st[1].insert(0);
	st[2].insert(0);
	forn(1, i, n)
	{
		for(auto j : start[i-1])
			st[j.s].insert(i-1);
		int L, L2;
		L2 = max(*st[1].rbegin(), *st[2].rbegin()) + 1;
		L = L2;
		forn(0, j, 'z'-'a')
		{
			if(j > 0)
				dp[i][j] = (dp[i][j] + get(1, 1, n, L, i-1, j-1, 1)) % mod;
			if(j < 'z'-'a')
				dp[i][j] = (dp[i][j] + get(1, 1, n, L, i-1, j+1, 2)) % mod;
		}
		if(*st[1].rbegin() < *st[2].rbegin())
		{
			auto it = *st[1].rbegin() + 1;
			L = it;
			FOR(0, j, 'z'-'a')
				dp[i][j] = (dp[i][j] + get(1, 1, n, L, L2-1, j+1, 2)) % mod;
		}
		else
		if(*st[1].rbegin() > *st[2].rbegin())
		{
			auto it = *st[2].rbegin() + 1;
			L = it;
			forn(1, j, 'z'-'a')
				dp[i][j] = (dp[i][j] + get(1, 1, n, L, L2-1, j-1, 1)) % mod;
		}
		if(i == 1)
		{
			forn(0, j, 'z'-'a') dp[i][j] = 1;
		}
		/*cout << "      FOR   " << i << endl;
		forn(0, j, 'z'-'a') cout << (char)(j + 'a') << " " << dp[i][j] << endl;
		*/
		forn(0, j, 'z'-'a')
		{
			if(j > 0)
				temp[j] = (temp[j - 1] + dp[i][j]) % mod;
			else
				temp[j] = dp[i][j];
			upd(1, 1, n, i, temp[j], j, 1);
//			cout << "UPD " << i << " " << temp[j] << endl;
		}
		nfor(0, j, 'z'-'a')
		{
			if(j == 'z'-'a')
				temp[j] = dp[i][j];
			else
				temp[j] = (temp[j + 1] + dp[i][j]) % mod;
//			cout << "UPD " << i << " " << temp[j] << endl;
			upd(1, 1, n, i, temp[j], j, 2);
		}
/*		o
		for(auto j : st[1]) cout << j << " ";
		cout << endl;
		for(auto j : st[2]) cout << j << " ";
		cout << endl;
		for(auto j : fin[i]) cout << j.f << " " << j.s << endl;
		cout << endl;*/
		for(auto j : fin[i])
			st[j.s].erase(st[j.s].find(j.f));
	}
	int ans = 0;
	forn(1, i, n)
	{
		forn(0, j, 'z'-'a') ans = (ans + dp[i][j]) % mod;
	}
	cout << ans;
}

Compilation message (stderr)

misspelling.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main()
      | ^~~~

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