#include<bits/stdc++.h> using namespace std; // define bool M1; //#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; #define memory cerr << abs(&M2 - &M1)/1024.0/1024 << " MB" << "\n" #define ll long long #define ii pair <int , int> #define iii pair <int , ii> #define se second #define fi first #define all(v) (v).begin() , (v).end() #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin()) #define bit(x,i) (((x) >> (i)) & 1LL) #define flip(x,i) ((x) ^ (1LL << (i))) #define ms(d,x) memset(d , x , sizeof(d)) #define exist __exist #define ends __ends #define visit visited #define left __left #define right __right #define prev __prev #define next __next #define sitingfake 1 #define orz 1 //constant const long long mod = 1e9 + 7; const long long linf = 4557430888798830399LL; const long long nlinf = -4485090715960753727LL; const int inf = 1061109567; const int ninf = -1044266559; const int dx[] = {0 , -1 , 0 , 1}; const int dy[] = {-1 , 0 , 1 , 0}; template<typename T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } template<typename T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } void Plus(ll & a ,ll b) { b %= mod; a += b; if(a < 0) a += mod; a %= mod; return; } void Mul(ll & a, ll b) { (a *= (b % mod)) %= mod; return; } //code const int maxn = 5e5 + 7; int n , m; int a[maxn] , b[maxn]; namespace sub2 { int Max[202][2]; int left[202] , right[202]; bool type[202]; bool free[202]; int dp[202][202][26][2]; void printAns(int i) { int ans = 0; for(int j = 1; j <= n; j++) { for(int c = 0; c <= 25; c++) { (ans += dp[i][j][c][0]) %= mod; (ans += dp[i][j][c][1]) %= mod; } } cout << ans << endl; } void solve() { for(int i = 1; i <= m; i++) { if(a[i] < b[i]) { Max[a[i]][0] = max(Max[a[i]][0] , b[i]); } else { swap(a[i] , b[i]); Max[a[i]][1] = max(Max[a[i]][1] , b[i]); } } for(int i = 1; i <= n; i++) { right[i] = max({Max[i][0] , Max[i][1] , i}); left[i] = max(min(Max[i][0] , Max[i][1]) , i); if(Max[i][0] && Max[i][1]) { if(left[i] == Max[i][0]) type[i] = 1; } else if(Max[i][1]) type[i] = 1; if(left[i] == i && right[i] == i) free[i] = 1; } for(int i = 0; i <= 25; i ++) dp[n][n][i][0] = 1; // 0 la < , 1 la > for(int i = n - 1; i >= 1; i--) { for(int j = max(left[i] , i + 1); j <= n; j++) { for(int k = 0; k <= 25; k++) { if(j < right[i]) { dp[i][j][k][!type[i]] = dp[i + 1][j][k][!type[i]]; } else { dp[i][j][k][0] = dp[i + 1][j][k][0]; if(dp[i][j][k][0] >= mod) dp[i][j][k][0] -= mod; dp[i][j][k][1] = dp[i + 1][j][k][1]; if(dp[i][j][k][1] >= mod) dp[i][j][k][1] -= mod; } } } if(free[i]) { int sum = 0; for(int c = 0; c <= 25; c++) { dp[i][i][c][1] = sum; for(int j = i + 1; j <= n; j++) { sum += dp[i + 1][j][c][0]; if(sum >= mod) sum -= mod; sum += dp[i + 1][j][c][1]; if(sum >= mod) sum -= mod; } } sum = 0; for(int c = 25; c >= 0; c--) { dp[i][i][c][0] = sum; for(int j = i + 1; j <= n; j++) { sum += dp[i + 1][j][c][0]; if(sum >= mod) sum -= mod; sum += dp[i + 1][j][c][1]; if(sum >= mod) sum -= mod; } } } else if(left[i] == i) { if(type[i] == 0) { int sum = 0; for(int c = 0; c <= 25; c++) { dp[i][i][c][1] = sum; for(int j = i + 1; j <= n; j++) { sum += dp[i + 1][j][c][1]; if(sum >= mod) sum -= mod; sum += dp[i + 1][j][c][0]; if(sum >= mod) sum -= mod; } } } else { int sum = 0; for(int c = 25; c >= 0; c--) { dp[i][i][c][0] = sum; for(int j = i + 1; j <= n; j++) { sum += dp[i + 1][j][c][1]; if(sum >= mod) sum -= mod; sum += dp[i + 1][j][c][0]; if(sum >= mod) sum -= mod; } } } } } int ans = 0; for(int i = 1; i <= n; i++) { for(int c = 0; c <= 25; c++) { ans += dp[1][i][c][0]; if(ans >= mod) ans -= mod; ans += dp[1][i][c][1]; if(ans >= mod) ans -= mod; } } //cout << ans; } } namespace sub4 { int Max[20002][2]; int left[20002] , right[20002]; bool type[20002]; bool free[20002]; int st[26][2][20002 * 4]; bool tag[26][2][20002 * 4]; void Push(int i , int t , int f) { if(tag[t][f][i]) { st[t][f][i * 2] = st[t][f][i * 2 + 1] = 0; tag[t][f][i * 2] = tag[t][f][i * 2 + 1] = 1; tag[t][f][i] = 0; return; } } void Set(int i , int l , int r , int u , int v , int t , int f) { if(u > r || v < l || st[t][f][i] == 0) return ; if(u <= l && r <= v) { st[t][f][i] = 0; tag[t][f][i] = 1; return; } int mid = (r + l) >> 1; Push(i , t , f); Set(i * 2 , l , mid , u , v , t , f); Set(i * 2 + 1 , mid + 1 , r , u , v , t , f); st[t][f][i] = st[t][f][i * 2] + st[t][f][i * 2 + 1]; if(st[t][f][i] >= mod) st[t][f][i] -= mod; } void up(int i , int l , int r ,int pos , int t , int f , int val) { if(pos > r || pos < l) return; if(l == r) { st[t][f][i] += val; if(st[t][f][i] >= mod) st[t][f][i] -= mod; return; } int mid = (l + r) >> 1; Push(i , t , f); up(i * 2 , l , mid , pos , t , f , val); up(i * 2 + 1 , mid + 1 , r , pos , t , f , val); st[t][f][i] = st[t][f][i * 2] + st[t][f][i * 2 + 1]; if(st[t][f][i] >= mod) st[t][f][i] -= mod; } int get(int i , int l , int r , int u , int v , int t , int f) { if(u > r || v < l) return 0; if(u <= l && r <= v) return st[t][f][i]; int mid = (r + l) >> 1; Push(i , t , f); int val = get(i * 2 , l , mid , u , v , t , f); val += get(i * 2 + 1 , mid + 1 , r , u , v , t , f); if(val >= mod) val -= mod; return val; } void solve() { for(int i = 1; i <= m; i++) { if(a[i] < b[i]) { Max[a[i]][0] = max(Max[a[i]][0] , b[i]); } else { swap(a[i] , b[i]); Max[a[i]][1] = max(Max[a[i]][1] , b[i]); } } for(int i = 1; i <= n; i++) { right[i] = max({Max[i][0] , Max[i][1] , i}); left[i] = max(min(Max[i][0] , Max[i][1]) , i); if(Max[i][0] && Max[i][1]) { if(left[i] == Max[i][0]) type[i] = 1; } else if(Max[i][1]) type[i] = 1; if(left[i] == i && right[i] == i) free[i] = 1; } for(int c = 0; c <= 25; c++) { up(1 , 1 , n , n , c , 0 , 1); } for(int i = n - 1; i >= 1; i--) { if(free[i]) { int sum = 0; for(int c = 0 ; c <= 25; c++) { up(1 , 1 , n , i , c , 1 , sum); sum += get(1 , 1 , n , i + 1 , n , c , 0); if(sum >= mod) sum -= mod; sum += get(1 , 1 , n , i + 1 , n , c , 1); if(sum >= mod) sum -= mod; } sum = 0; for(int c = 25; c >= 0; c--) { up(1 , 1 , n , i , c , 0 , sum); sum += get(1 , 1 , n , i + 1 , n , c , 0); if(sum >= mod) sum -= mod; sum += get(1 , 1 , n , i + 1 , n , c , 1); if(sum >= mod) sum -= mod; } } else if(left[i] == i) { if(!type[i]) { int sum = 0; for(int c = 0 ; c <= 25; c++) { up(1 , 1 , n , i , c , 1 , sum); sum += get(1 , 1 , n , i + 1 , n , c , 0); if(sum >= mod) sum -= mod; sum += get(1 , 1 , n , i + 1 , n , c , 1); if(sum >= mod) sum -= mod; } } else { int sum = 0; for(int c = 25; c >= 0; c--) { up(1 , 1 , n , i , c , 0 , sum); sum += get(1 , 1 , n , i + 1 , n , c , 0); if(sum >= mod) sum -= mod; sum += get(1 , 1 , n , i + 1 , n , c , 1); if(sum >= mod) sum -= mod; } } } for(int c = 0; c <= 25; c++) { if(i + 1 <= left[i] - 1) { Set(1 , 1 , n , i + 1, left[i] - 1 , c , 0); Set(1 , 1 , n , i + 1, left[i] - 1 , c , 1); } if(max(left[i] , i + 1) < right[i]) { Set(1 , 1 , n , max(left[i] , i + 1) , right[i] - 1 , c , type[i]); } } } int ans = 0; for(int c = 0; c <= 25; c++) { ans += st[c][0][1]; if(ans >= mod) ans -= mod; ans += st[c][1][1]; if(ans >= mod) ans -= mod; } cout << ans; } } namespace sub5 { stack <int> st[26][2]; int sum[26][2]; int dp[maxn][26][2]; int Max[maxn][2]; int left[maxn] , right[maxn]; bool type[maxn]; bool free[maxn]; void solve() { for(int i = 1; i <= m; i++) { if(a[i] < b[i]) { Max[a[i]][0] = max(Max[a[i]][0] , b[i]); } else { swap(a[i] , b[i]); Max[a[i]][1] = max(Max[a[i]][1] , b[i]); } } for(int i = 1; i <= n; i++) { right[i] = max({Max[i][0] , Max[i][1] , i}); left[i] = max(min(Max[i][0] , Max[i][1]) , i); if(Max[i][0] && Max[i][1]) { if(left[i] == Max[i][0]) type[i] = 1; } else if(Max[i][1]) type[i] = 1; if(left[i] == i && right[i] == i) free[i] = 1; } for(int c = 0; c <= 25; c++) { dp[n][c][0] = 1; st[c][0].push(n); sum[c][0]++; } for(int i = n - 1; i >= 1; i--) { //cout << i << endl; if(free[i]) { //cout << i << endl; int s = 0; for(int c = 0; c <= 25; c++) { dp[i][c][1] = s; s += sum[c][0]; if(s >= mod) s -= mod; s += sum[c][1]; if(s >= mod) s -= mod; } s = 0; for(int c = 25; c >= 0; c--) { dp[i][c][0] = s; s += sum[c][0]; if(s >= mod) s -= mod; s += sum[c][1]; if(s >= mod) s -= mod; } } else if(left[i] == i) { if(!type[i]) { int s = 0; for(int c = 0; c <= 25; c++) { dp[i][c][1] = s; s += sum[c][0]; if(s >= mod) s -= mod; s += sum[c][1]; if(s >= mod) s -= mod; } } else { int s = 0; for(int c = 25; c >= 0; c--) { dp[i][c][0] = s; s += sum[c][0]; if(s >= mod) s -= mod; s += sum[c][1]; if(s >= mod) s -= mod; } } } for(int c = 0; c <= 25; c++) { if(i + 1 <= left[i] - 1) { while(!st[c][0].empty() && st[c][0].top() <= left[i] - 1) { sum[c][0] = (sum[c][0] - dp[st[c][0].top()][c][0] + mod) % mod; st[c][0].pop(); } while(!st[c][1].empty() && st[c][1].top() <= left[i] - 1) { sum[c][1] = (sum[c][1] - dp[st[c][1].top()][c][1] + mod) % mod; st[c][1].pop(); } } if(max(left[i] , i + 1) < right[i]) { while(!st[c][type[i]].empty() && st[c][type[i]].top() < right[i]) { sum[c][type[i]] = (sum[c][type[i]] - dp[st[c][type[i]].top()][c][type[i]] + mod) % mod; st[c][type[i]].pop(); } } if(dp[i][c][0]) { st[c][0].push(i); sum[c][0] += dp[i][c][0]; if(sum[c][0] >= mod) sum[c][0] -= mod; } if(dp[i][c][1]) { st[c][1].push(i); sum[c][1] += dp[i][c][1]; if(sum[c][1] >= mod) sum[c][1] -= mod; } } } int ans = 0; for(int c = 0; c <= 25; c++) { ans += sum[c][0]; if(ans >= mod) ans -= mod; ans += sum[c][1]; if(ans >= mod) ans -= mod; } cout << ans; } } void solve(void) { cin >> n >> m; for(int i = 1; i <= m; i++) { cin >> a[i] >> b[i]; } if(n <= 200) return sub2 :: solve(); if(n <= 20000) return sub4 :: solve(); return sub5 :: solve(); } bool M2; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int tc = 1; // cin >> tc; while(tc--) solve(); // execute; // memory; }

misspelling.cpp: In function 'int main()':
misspelling.cpp:574:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  574 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
misspelling.cpp:575:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  575 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~