제출 #1132627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132627		Math4Life2020	Misspelling (JOI22_misspelling)	C++20	100 / 100	635 ms	220372 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll p = 1e9+7;
const ll Nm = 524288; const ll E = 19;
const ll K = 26;

ll dpU[Nm][K]; //dp up
ll dpD[Nm][K]; //dp down

ll stU[2*Nm]; //segtree of jump up (increase)
ll stD[2*Nm]; //segtree of jump down (decrease)

void wtU(ll a, ll b) {
	ll sp = a+Nm;
	do {
		stU[sp]=max(stU[sp],b); sp=sp/2;
	} while (sp>0);
}

inline ll v2(ll x) {
	return __builtin_ctz(x);
}

ll rdU(ll l, ll r) {
	if (l>r) {return -1;}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		return max(stU[(l>>vl)+(1<<(E-vl))],rdU(l+(1<<vl),r));
	} else {
		return max(stU[(r>>vr)+(1<<(E-vr))],rdU(l,r-(1<<vr)));
	}
}

ll rdD(ll l, ll r) {
	if (l>r) {return -1;}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		return max(stD[(l>>vl)+(1<<(E-vl))],rdD(l+(1<<vl),r));
	} else {
		return max(stD[(r>>vr)+(1<<(E-vr))],rdD(l,r-(1<<vr)));
	}
}

void wtD(ll a, ll b) {
	ll sp = a+Nm;
	do {
		stD[sp]=max(stD[sp],b); sp=sp/2;
	} while (sp>0);
}

int main() {
	ll ans = 0;
	ll N,M; cin >> N >> M;
	for (ll i=Nm;i<(2*Nm);i++) {
		stU[i]=i-Nm;
		stD[i]=i-Nm;
	}
	for (ll ps=(Nm-1);ps>=1;ps--) {
		stU[ps]=max(stU[2*ps],stU[2*ps+1]);
		stD[ps]=max(stD[2*ps],stD[2*ps+1]);
	}
	for (ll m=0;m<M;m++) {
		ll a,b; cin >> a >> b; a--; b--; //T_a <= T_b
		if (a<b) {
			wtU(a,b); //T_b is higher aka next char is down
		} else {
			wtD(b,a);
		}
	}
	for (ll i=(Nm-1);i>=0;i--) {
		wtU(i,rdU(i,stU[i+Nm]));
		wtD(i,rdD(i,stD[i+Nm]));
	}
	for (ll i=0;i<=N;i++) {
		for (ll k=0;k<K;k++) {
			dpU[i][k]=0;
			dpD[i][k]=0;
		}
	}
	for (ll i=0;i<N;i++) {
		vector<ll> dpV(K,0);
		if (i==0) {
			for (ll k=0;k<K;k++) {
				dpV[k]=1;
			}
		} else {
			ll psup = 0;
			for (ll k=0;k<K;k++) {
				dpV[k]+=psup;
				psup += dpU[i][k]; psup %= p;
			}
			ll psdn = 0;
			for (ll k=(K-1);k>=0;k--) {
				dpV[k]+=psdn;
				psdn += dpD[i][k]; psdn %= p;
			}
		}
		for (ll k=0;k<K;k++) {
			ans = (ans+dpV[k])%p;
			dpU[i][k] += dpV[k]; dpU[i][k]%=p;
			dpU[1+stD[i+Nm]][k] = (dpU[1+stD[i+Nm]][k]+dpU[i][k])%p;
			dpD[i][k] += dpV[k]; dpD[i][k]%=p;
			dpD[1+stU[i+Nm]][k] = (dpD[1+stU[i+Nm]][k]+dpD[i][k])%p;
		}
	}
	cout << ans << "\n";
}

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