제출 #1017449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017449		Unforgettablepl	Misspelling (JOI22_misspelling)	C++17	100 / 100	597 ms	183888 KiB

misspelling

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

#define int long long

const int modulo = 1e9+7;

int32_t main(){
	int n,m;
	cin >> n >> m;
	vector<vector<pair<bool,int>>> constrains(n+1);
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		if(a<b){
			constrains[a].emplace_back(false,b);
		} else {
			constrains[b].emplace_back(true,a);
		}
	}
	set<int> activelower;
	set<int> activeupper;
	vector<int> DPlow(28),DPhigh(28);
	vector<vector<int>> DP(n+1,vector<int>(28));
	auto remove = [&](bool type,int x){
		if(type){
			while(!activelower.empty() and *activelower.begin()<=x){
				int curr = *activelower.begin();
				activelower.erase(activelower.begin());
				int tot = 0;
				for(int i=1;i<=26;i++){
					tot+=DP[curr][i];
					tot%=modulo;
					DPlow[i]=(DPlow[i]-tot+modulo)%modulo;
				}
			}
		} else {
			while(!activeupper.empty() and *activeupper.begin()<=x){
				int curr = *activeupper.begin();
				activeupper.erase(activeupper.begin());
				int tot = 0;
				for(int i=26;i;i--){
					tot+=DP[curr][i];
					tot%=modulo;
					DPhigh[i]=(DPhigh[i]-tot+modulo)%modulo;
				}
			}
		}
	};
	for(int x=n;x;x--){
		for(auto&[a,b]:constrains[x])remove(a,b);
		for(int j=1;j<=26;j++){
			DP[x][j] = (DPlow[j-1]+DPhigh[j+1]+1ll)%modulo;
		}
		activelower.insert(x);
		activeupper.insert(x);
		int tot = 0;
		for(int i=1;i<=26;i++){
			tot+=DP[x][i];
			tot%=modulo;
			DPlow[i]+=tot;
			DPlow[i]%=modulo;
		}
		tot = 0;
		for(int i=26;i;i--){
			tot+=DP[x][i];
			tot%=modulo;
			DPhigh[i]+=tot;
			DPhigh[i]%=modulo;
		}
	}
	int ans = 0;
	for(int i=1;i<=26;i++)ans+=DP[1][i];
	cout << (ans%modulo) << '\n';
}

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