Submission #1178334

#TimeUsernameProblemLanguageResultExecution timeMemory
1178334ace5Misspelling (JOI22_misspelling)C++20
100 / 100
277 ms247020 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 500005; const int mod = 1000000007; const int maxlog = 19; const int alf = 26; int add(int a,int b) { return a+b >= mod ? a+b-mod : a+b; } vector<pair<int,int>> st[2]; int dp[2][alf][maxn],pref[alf+1][maxn],suf[alf+1][maxn]; vector<int> r[2][maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n,m; cin >> n >> m; for(int i = 0;i < m;++i) { int a,b; cin >> a >> b; a--; b--; if(a < b) r[1][a].push_back(b-1); else r[0][b].push_back(a-1); } int maxr[2][n]; for(int j = n-1;j >= 0;--j) { for(int y = 0;y < 2;++y) { int rg = j-1; for(int u = 0;u < r[y][j].size();++u) { rg = max(rg,r[y][j][u]); } while(st[y].size() && st[y].back().first <= rg+1) { rg = max(rg,st[y].back().second); st[y].pop_back(); } maxr[y][j] = rg+1; if(rg >= j) st[y].push_back({j,rg}); } } for(int j = n-1;j >= 0;--j) { for(int c = 0;c < alf;++c) { for(int y = 0;y < 2;++y) { if(j == n-1) dp[y][c][j] = 0; else { if(maxr[y][j] != j) dp[y][c][j] = dp[y][c][maxr[y][j]]; else { dp[y][c][j] = add(dp[y][c][j+1],y ? suf[c+1][j+1] : pref[c][j+1]); } } } pref[c+1][j] = add(pref[c][j],add(dp[0][c][j],dp[1][c][j]+1)); } for(int c = alf-1;c >= 0;--c) suf[c][j] = add(suf[c+1][j],add(dp[0][c][j],dp[1][c][j]+1)); } cout << pref[alf][0]; }
#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...