제출 #702481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702481		emptypringlescan	Misspelling (JOI22_misspelling)	C++17	8 / 100	423 ms	222348 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
//we are perpetually trapped in a cycle of death and rebirth
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int lefu[n],lefd[n];
    memset(lefu,-1,sizeof(lefu));
    memset(lefd,-1,sizeof(lefd));
    vector<pair<int,int> > rangu,rangd;
    for(int i=0; i<m; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		if(a<b) rangd.push_back({a,b});
		else rangu.push_back({b,a});
	}
	sort(rangd.begin(),rangd.end());
	sort(rangu.begin(),rangu.end());
	stack<pair<int,int> > s;
	int c1=0,c2=0;
	for(int i=0; i<n; i++){
		while(!s.empty()&&s.top().second<i){
			s.pop();
		}
		while(c1<(int)rangd.size()&&rangd[c1].first<i){
			s.push(rangd[c1]);
			c1++;
		}
		if(!s.empty()) lefd[i]=s.top().first;
	}
	while(!s.empty()){
		s.pop();
	}
	for(int i=0; i<n; i++){
		while(!s.empty()&&s.top().second<i){
			s.pop();
		}
		while(c2<(int)rangu.size()&&rangu[c2].first<i){
			s.push(rangu[c2]);
			c2++;
		}
		if(!s.empty()) lefu[i]=s.top().first;
	}
	long long dv[n][26],v[n][26];
	memset(dv,0,sizeof(dv));
	memset(v,0,sizeof(v));
	for(int i=0; i<26; i++){
		v[0][i]=0;
		dv[0][i]=1;
	}
	long long ts[500005];
	ts[0]=1;
	for(int i=1; i<500005; i++){
		ts[i]=ts[i-1]*26%1000000007;
	}
	for(int i=1; i<n; i++){
		long long cur=0,sum=0;
		for(int j=0; j<26; j++) sum=(sum+v[i-1][j])%1000000007;
		for(int j=25; j>=0; j--){
			v[i][j]+=sum;
			if(v[i][j]>=1000000007) v[i][j]-=1000000007;
			if(lefu[i]==-1) continue;
			if(j<25) cur+=dv[lefu[i]][j+1];
			v[i][j]+=cur;
			if(v[i][j]>=1000000007) v[i][j]-=1000000007;
		}
		cur=0;
		for(int j=0; j<26; j++){
			if(lefd[i]==-1) continue;
			if(j) cur+=dv[lefd[i]][j-1];
			v[i][j]+=cur;
			if(v[i][j]>=1000000007) v[i][j]-=1000000007;
		}
		for(int j=0; j<26; j++){
			dv[i][j]=ts[i]-v[i][j][phone];
			if(dv[i][j]>=1000000007) dv[i][j]-=1000000007;
			//cout << v[i][j] << ' ' << dv[i][j] << '\n';
		}
	}
	long long ans=0,bru=0;
	for(int i=0; i<26; i++) ans=(ans+dv[n-1][i])%1000000007;
	for(int i=0; i<26; i++) bru=(bru+v[n-1][i])%1000000007;
	cout << ans;
}

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