제출 #720612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720612		Abrar_Al_Samit	Misspelling (JOI22_misspelling)	C++17	100 / 100	376 ms	144716 KiB

misspelling

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

const int mod = 1e9 + 7;
const int nax = 5e5 + 3;
int n, m;

int s[nax], g[nax];
long long dp[nax][26];
long long sum_s[26], sum_g[26];
void PlayGround() {
	cin>>n>>m;
	for(int i=1; i<=m; ++i) {
		int x, y;
		cin>>x>>y;
		if(x<y) {
			s[x] = max(s[x], y);
		} else {
			g[y] = max(g[y], x);
		}
	}
	for(int i=0; i<26; ++i) {
		dp[n][i] = 1;
	}

	set<int>alive_s, alive_g;
	for(int i=n-1; i>0; --i) {
		alive_s.insert(i+1);
		alive_g.insert(i+1);

		//add i+1 to sum_s and sum_g
		for(int k=0; k<26; ++k) {
			sum_s[k] += dp[i+1][k];
			sum_g[k] += dp[i+1][k];
		}

		//remove invalid j's
		while(!alive_g.empty() && *alive_g.begin()<=s[i]) {
			int j = *alive_g.begin();
			alive_g.erase(j);

			//remove from sum_g
			for(int k=0; k<26; ++k) {
				sum_g[k] -= dp[j][k];
			}
		}
		while(!alive_s.empty() && *alive_s.begin()<=g[i]) {
			int j = *alive_s.begin();
			alive_s.erase(j);

			//remove from sum_s
			for(int k=0; k<26; ++k) {
				sum_s[k] -= dp[j][k];
			}
		}

		//calculate dp[i]

		for(int k=0; k<26; ++k) {
			dp[i][k] = 1;
		}
		long long val = 0;
		for(int k=0; k<26; ++k) {
			dp[i][k] += val;
			val += sum_s[k];
		}
		val = 0;
		for(int k=25; k>=0; --k) {
			dp[i][k] += val;
			val += sum_g[k];
		}
		for(int k=0; k<26; ++k) {
			dp[i][k] %= mod;
		}
	}
	long long ans = 0;
	for(int i=0; i<26; ++i) {
		ans += dp[1][i];
	}
	ans %= mod;
	cout<<ans<<'\n';

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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