Submission #1321500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321500		salmon	Misspelling (JOI22_misspelling)	C++20	100 / 100	412 ms	125600 KiB

misspelling

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

int N;
int M;
int l[500100];
int g[500100];
long long int mod = 1'000'000'007;
int nxt[2][500100];
int v[2][500100][30];
vector<int> va;

void update(int i, int num, bool flag){
	int it = nxt[flag][i - 1];
	
	while(it <= num && it != -1){
		if(!flag){
			for(int i = 1; i <= 26; i++){
				va[i] = (va[i] - v[flag][it][i - 1] + mod) % mod;
			}
		}
		else{
			for(int i = 1; i <= 26; i++){
				va[i] = (va[i] - v[flag][it][i + 1] + mod) % mod;
			}
		}
		it = nxt[flag][it];
	}
	
	nxt[flag][i - 1] = it; 
}

int main(){
	//while(true){
	scanf(" %d",&N);
	scanf(" %d",&M);
	
	for(int i = 0; i < N; i++){
		l[i] = i - 1;
		g[i] = i - 1;
	}
	
	for(int i = 1; i < N; i++){
		nxt[0][i] = i + 1;
		nxt[1][i] = i + 1;
	}
	nxt[0][N] = -1;
	nxt[1][N] = -1;
	
	for(int i = 0; i < M; i++){
		int u, v;
		
		scanf(" %d",&u);
		scanf(" %d",&v);
		
		if(u > v){
			l[v] = max(l[v],u);
		}
		else{
			g[u] = max(g[u],v);
		}
	}
	
	v[0][N][0] = 0;
	v[1][N][27] = 0;
	for(int i = 1; i <= 26; i++){
		v[0][N][i] = i;
		v[1][N][i] = 26 - i + 1;
	}
	
	
	for(int i = 0; i <= 26; i++) va.push_back(26);
	va[0] = 0;
	
	for(int i = N - 1; i >= 1; i--){
		update(i + 1,g[i],0);
		update(i + 1,l[i],1);
		
		
		if(i == 1) break;
		
		v[0][i][0] = 0;
		v[0][i][27] = 0;
		for(int k = 1; k <= 26; k++){
			v[0][i][k] = (v[0][i][k - 1] + va[k]) % mod; 
		}
		 
		v[1][i][0] = 0;
		v[1][i][27] = 0;
		for(int k = 26; k >= 1; k--){
			v[1][i][k] = (v[1][i][k + 1] + va[k]) % mod; 
		}
		
		for(int k = 1; k <= 26; k++){
			va[k] = (v[0][i][k - 1] + va[k]) % mod; 
			va[k] = (v[1][i][k + 1] + va[k]) % mod; 
		}
	}
	
	
	long long int ans = 0;
	for(int i : va){
		ans += i;
	}
	//printf("\n");
	
	printf("%lld\n",ans % mod);
//}
}
/*
10 8
2 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
 */

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
misspelling.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
misspelling.cpp:53:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
misspelling.cpp:54:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~

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