제출 #930474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930474		asdf1234coding	Misspelling (JOI22_misspelling)	C++14	100 / 100	471 ms	119284 KiB

misspelling

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

#define int long long
#define vi vector<int>
#define pb push_back

bool ckmax(int &a, int b) {return a<b?a=b,true:false;}

const int MA = 26;
const int MOD = 1e9+7;

int32_t main() {
	int n,m; cin>>n>>m;
	vi reqL(n+1), reqR(n+1);
	for(int i=0; i<m; i++) {
		int a, b; cin>>a>>b;
		if(a<b) {
			ckmax(reqL[a], b);
			// means that [a+1, b] is ====V
			// equal and then down
		} else {
			ckmax(reqR[b], a);
			// means that [b+1, a] is =======^
			// equal and then up
		}
	}
	vi suf(MA);
	vi processL, processR;
	int dp[n+4][MA];
	for(int i=n; i>=1; i--) {
		// cout<<"i is "<<i<<endl;
		if(reqL[i]) {
			while(processL.size() && processL.back()<=reqL[i]) {
				int cum=0;
				for(int j=0; j<MA; j++) {
					// subtracts lower stuff since has to go down
					suf[j]-=cum;
					cum+=dp[processL.back()][j];
					suf[j]%=MOD; cum%=MOD;
				}
				processL.pop_back();
			}
		}
		if(reqR[i]) {
			while(processR.size() && processR.back() <= reqR[i]) {
				int cum=0;
				for(int j=MA-1; j>=0; j--) {
					suf[j]-=cum; cum+=dp[processR.back()][j];
					suf[j]%=MOD; cum%=MOD;
				}
				processR.pop_back();
			}
		}
		int nw=0;
		for(int j=0; j<MA; j++) {
			dp[i][j]=suf[j]+1;
			nw+=dp[i][j];
			dp[i][j]%=MOD; nw%=MOD;
		}
		for(int j=0; j<MA; j++) {
			suf[j]+=nw; suf[j]-=dp[i][j];
			suf[j]%=MOD;
		}
		processL.pb(i);
		processR.pb(i);
	}
	int ret=0;
	for(int i=0; i<MA; i++) {
		ret+=dp[1][i]; ret%=MOD;
	}
	cout<<(ret+MOD)%MOD<<endl;
}

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