Submission #1321490

#TimeUsernameProblemLanguageResultExecution timeMemory
1321490salmonMisspelling (JOI22_misspelling)C++20
100 / 100
3898 ms286116 KiB
#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;

struct node{
	
	int s,e,m;
	bool lazy[2];
	int v[2][30];	
	node *l,*r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;

		lazy[0] = false;
		lazy[1] = false;
		
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
	}
	
	void update(int i, vector<int> k){
		if(s == e){
			v[0][0] = 0;
			v[1][27] = 0;
			
			for(int j = 1; j <= 26; j++) v[0][j] = (v[0][j - 1] + k[j] + 1) % mod;
			for(int j = 26; j >= 1; j--) v[1][j] = (v[1][j + 1] + k[j] + 1) % mod;
			
			return;
		}
		
		if(i <= m) l -> update(i,k);
		else r -> update(i,k);
		
		
		
		for(int i = 0; i <= 27; i++){
			v[0][i] = ((l -> v[0][i]) + (r -> v[0][i]))%mod;
			v[1][i] = ((l -> v[1][i]) + (r -> v[1][i]))%mod;
		}
	}
	
	void updatel(int S, int E, bool flag){
		if(lazy[flag]) return;
		
		if(S <= s && e <= E){
			if(lazy[flag]) return;
			
			lazy[flag] = true;
			
			for(int i = 0; i <= 27; i++){
				v[flag][i] = 0;
			}
			
			return;
		}
		
		if(S <= m){
			l -> updatel(S,E,flag);
		}
		if(m < E){
			r -> updatel(S,E,flag);
		}
		
		int *vl = l -> v[flag];
		int *vr = r -> v[flag];
		
		for(int i = 0; i <= 27; i++){
			v[flag][i] = (vl[i] + vr[i])%mod;
		}
	}
	
	vector<int> query(int S, bool lazy0, bool lazy1){
		lazy0 |= lazy[0];
		lazy1 |= lazy[1];
		
		if(S <= s){
			vector<int> temp = {0};
			
			for(int i = 1; i <= 26; i++){
				temp.push_back((v[0][i - 1] * (1-lazy0) + v[1][i + 1] * (1-lazy1)) % mod);
			}
			
			return temp;
		}
		
		if(S <= m){
			vector<int> temp = r -> query(S,lazy0,lazy1);
			vector<int> temp1 = l -> query(S,lazy0,lazy1);
		
			for(int i = 0; i < temp.size(); i++){
				temp[i] = (temp[i] + temp1[i]) % mod;
			}
			
			return temp;
		}
		else return r -> query(S,lazy0,lazy1);
	}
}*root;



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 = 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);
		}
	}
	
	root = new node(1,N);
	
	vector<int> v = {0};
	for(int i = 1; i <= 26; i++) v.push_back(0);
	
	root -> update(N,v);
	
	for(int i = N - 1; i >= 1; i--){
		if(g[i] != i - 1) root -> updatel(i + 1,g[i],0);
		if(l[i] != i - 1) root -> updatel(i + 1,l[i],1);
		
		
		if(i == 1) break;
		root -> update(i,root -> query(i + 1,false,false));
	}
	
	vector<int> b = root -> query(2,false,false);
	
	
	long long int ans = 0;
	for(int i : b){
		ans += i;
		//printf("%d ",i);
	}
	//printf("\n");
	
	ans = (ans + 26) % mod;

	printf("%lld\n",ans);
//}
}
/*
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:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
misspelling.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
misspelling.cpp:126:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
misspelling.cpp:127:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...