Submission #956881

#TimeUsernameProblemLanguageResultExecution timeMemory
956881hotboy2703Misspelling (JOI22_misspelling)C++14
100 / 100
787 ms389860 KiB
//assert,cout,dau // , endl,function chua reference vector,chua pragma log, builtinpopcount,bitset,... #include<bits/stdc++.h> using ll = long long; using namespace std; #define pll pair <ll,ll> #define fi first #define se second #define sz(a) (ll((a).size())) #define BIT(mask,i) (((mask) >> (i))&1) #define MASK(i) (1LL << (i)) #define MP make_pair const ll MOD = 1e9 + 7; const ll MAXN = 5e5; const ll base = 26; ll cond[MAXN+100][2]; stack <pll> s[base][2]; ll sum[base][2]; ll pre_sum[base][2]; ll sus[base]; ll n,m; int main(){ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr); cin>>n>>m; for (ll i = 1;i <= m;i ++){ ll u,v; cin>>u>>v; ll l = min(u,v),r = max(u,v); cond[l][u < v] = max(cond[l][u < v],r); } auto mod = [&](ll &x,ll y) -> void{ // cout<<x<<' '<<y<<'\n'; x += y; if (x >= MOD)x -= MOD; if (x < 0)x += MOD; }; auto mod2 = [&](ll x,ll y) -> ll{ mod(x,y); return x; }; auto add = [&](ll x,ll y,ll id,ll z){ s[x][y].push(MP(id,z)); mod(sum[x][y],z); }; auto del = [&](ll x,ll y){ mod(sum[x][y],-s[x][y].top().se); s[x][y].pop(); }; for (ll i = 0;i < base;i ++){ add(i,0,n,1); } // for (ll j = 0;j < base;j ++){ // cout<<"CHAR "<<char('a'+ j)<<' '; // for (ll k = 0;k < 2;k ++){ // cout<<sum[j][k]<<' '; // } // cout<<'\n'; // } for (ll i = n - 1;i >= 1;i --){ for (ll j = 0;j < base;j ++)sus[j] = mod2(sum[j][0],sum[j][1]); for (ll j = base - 1; j >= 0;j --){ if (j + 1 < base)pre_sum[j][0] = mod2(sus[j+1],pre_sum[j+1][0]); else pre_sum[j][0] = 0; } for (ll j = 0;j < base;j ++){ if (j)pre_sum[j][1] = mod2(sus[j-1],pre_sum[j-1][1]); else pre_sum[j][1] = 0; // cout<<j<<' '<<pre_sum[j][1]<<' '<<sus[j-1]<<' '<<pre_sum[j-1][1]<<'\n'; } for (ll j = 0;j < base;j ++){ for (ll k = 0;k < 2;k ++){ while (sz(s[j][k]) && s[j][k].top().fi < cond[i][!k])del(j,k); } } for (ll j = 0;j < base;j ++){ for (ll k = 0;k < 2;k ++){ if (cond[i][!k] == 0)add(j,k,i,pre_sum[j][k]); } } // for (ll j = 0;j < base;j ++){ // cout<<"CHAR "<<char('a'+j)<<' '; // for (ll k = 0;k < 2;k ++){ // cout<<sum[j][k]<<' '; // } // cout<<'\n'; // } // cout<<'\n'; } ll ans = 0; for (ll j = 0;j < base;j ++){ for (ll k = 0;k < 2;k ++){ mod(ans,sum[j][k]); } } cout<<ans; }
#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...