# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
548208 | 2022-04-12T17:34:34 Z | fcmalkcin | Misspelling (JOI22_misspelling) | C++17 | 1171 ms | 428952 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" #define pb push_back #define F(i,a,b) for(ll i=a;i<=b;i++) const ll maxn=5e5+100; const ll base=3e18; const ll mod= 1e9+7 ; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); /// have medal in APIO /// goal 2/8 ll a[maxn]; ll b[maxn]; ll dp[maxn][28]; ll cnt[28]; ll val[maxn][28]; ll val1[maxn][28]; vector<ll> adjp[maxn]; vector<ll> adjp1[maxn]; vector<ll> adj[maxn]; vector<ll> adj1[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ll n, m; cin>> n>> m; for (int i=1; i<=m; i++) { cin>> a[i]>> b[i]; if (a[i]<b[i]) { adj[b[i]].pb(a[i]+1); } else { adj1[a[i]].pb(b[i]+1); } } multiset<ll,greater<ll>> st; multiset<ll,greater<ll>> st1; for (int i=n; i>=1; i--) { for (auto to:adj[i]) { st.insert(to); } for (auto to:adj1[i]) { st1.insert(to); } while (st.size()&&(*st.begin())>i) { st.erase(st.begin()); } while (st1.size()&&(*st1.begin())>i) { st1.erase(st1.begin()); } ll pre=1; if (st.size()) pre=(*st.begin()); ll pre1=1; if (st1.size()) pre1=(*st1.begin()); adjp[pre1].pb(i); adjp1[pre].pb(i); // cout <<i<<" "<<pre<<" "<<pre1<<endl; } ll ans=0; for (int i=1; i<=26; i++) { dp[1][i]=1; } for (int i=1; i<=n; i++) { for (auto to:adjp[i]) { for (int t=1; t<=26; t++) { val[to][t]=cnt[t]; } } for (auto to:adjp1[i]) { for (int t=1; t<=26; t++) { val1[to][t]=cnt[t]; } } ll cntnw=0; for (int t=26;t>=1;t--) { dp[i][t]=(dp[i][t]+cntnw)%mod; cntnw=(cntnw+cnt[t]-val[i][t]+mod)%mod; if (i==2) { // cout <<dp[i][t]<<" "<<t<<" "<<cntnw<<" "<<cnt[t]<<" "<<val[i][t]<<" chk1"<<endl; } } cntnw=0; for (int t=1;t<=26;t++) { dp[i][t]=(dp[i][t]+cntnw)%mod; cntnw=(cntnw+cnt[t]-val1[i][t]+mod)%mod; if (i==2) { // cout <<dp[i][t]<<" "<<t<<" "<<cntnw<<" "<<cnt[t]<<" "<<val1[i][t]<<" chk2"<<endl; } } for (int t=1;t<=26;t++) { cnt[t]=(cnt[t]+dp[i][t])%mod; // if (i==2) cout <<dp[i][t]<<" chk1"<<endl; } } for (int i=1; i<=n; i++) for (int t=1; t<=26; t++) ans=(ans+dp[i][t])%mod; cout <<ans<<endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 47316 KB | Output is correct |
2 | Correct | 28 ms | 47224 KB | Output is correct |
3 | Correct | 27 ms | 47360 KB | Output is correct |
4 | Correct | 25 ms | 47304 KB | Output is correct |
5 | Correct | 24 ms | 47260 KB | Output is correct |
6 | Correct | 28 ms | 47232 KB | Output is correct |
7 | Correct | 28 ms | 47352 KB | Output is correct |
8 | Correct | 26 ms | 47312 KB | Output is correct |
9 | Correct | 28 ms | 47356 KB | Output is correct |
10 | Correct | 24 ms | 47348 KB | Output is correct |
11 | Correct | 25 ms | 47248 KB | Output is correct |
12 | Correct | 24 ms | 47316 KB | Output is correct |
13 | Correct | 26 ms | 47304 KB | Output is correct |
14 | Correct | 23 ms | 47316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 47316 KB | Output is correct |
2 | Correct | 28 ms | 47224 KB | Output is correct |
3 | Correct | 27 ms | 47360 KB | Output is correct |
4 | Correct | 25 ms | 47304 KB | Output is correct |
5 | Correct | 24 ms | 47260 KB | Output is correct |
6 | Correct | 28 ms | 47232 KB | Output is correct |
7 | Correct | 28 ms | 47352 KB | Output is correct |
8 | Correct | 26 ms | 47312 KB | Output is correct |
9 | Correct | 28 ms | 47356 KB | Output is correct |
10 | Correct | 24 ms | 47348 KB | Output is correct |
11 | Correct | 25 ms | 47248 KB | Output is correct |
12 | Correct | 24 ms | 47316 KB | Output is correct |
13 | Correct | 26 ms | 47304 KB | Output is correct |
14 | Correct | 23 ms | 47316 KB | Output is correct |
15 | Correct | 25 ms | 47572 KB | Output is correct |
16 | Correct | 24 ms | 47440 KB | Output is correct |
17 | Correct | 23 ms | 47452 KB | Output is correct |
18 | Correct | 24 ms | 47436 KB | Output is correct |
19 | Correct | 28 ms | 47440 KB | Output is correct |
20 | Correct | 24 ms | 47492 KB | Output is correct |
21 | Correct | 23 ms | 47456 KB | Output is correct |
22 | Correct | 28 ms | 47960 KB | Output is correct |
23 | Correct | 22 ms | 47444 KB | Output is correct |
24 | Correct | 25 ms | 47464 KB | Output is correct |
25 | Correct | 23 ms | 47444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 47332 KB | Output is correct |
2 | Correct | 30 ms | 47288 KB | Output is correct |
3 | Correct | 31 ms | 47292 KB | Output is correct |
4 | Correct | 23 ms | 47316 KB | Output is correct |
5 | Correct | 620 ms | 423772 KB | Output is correct |
6 | Correct | 589 ms | 423704 KB | Output is correct |
7 | Correct | 619 ms | 423456 KB | Output is correct |
8 | Correct | 613 ms | 423964 KB | Output is correct |
9 | Correct | 586 ms | 424104 KB | Output is correct |
10 | Correct | 51 ms | 62260 KB | Output is correct |
11 | Correct | 27 ms | 47440 KB | Output is correct |
12 | Correct | 25 ms | 47348 KB | Output is correct |
13 | Correct | 1091 ms | 428952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 47316 KB | Output is correct |
2 | Correct | 28 ms | 47224 KB | Output is correct |
3 | Correct | 27 ms | 47360 KB | Output is correct |
4 | Correct | 25 ms | 47304 KB | Output is correct |
5 | Correct | 24 ms | 47260 KB | Output is correct |
6 | Correct | 28 ms | 47232 KB | Output is correct |
7 | Correct | 28 ms | 47352 KB | Output is correct |
8 | Correct | 26 ms | 47312 KB | Output is correct |
9 | Correct | 28 ms | 47356 KB | Output is correct |
10 | Correct | 24 ms | 47348 KB | Output is correct |
11 | Correct | 25 ms | 47248 KB | Output is correct |
12 | Correct | 24 ms | 47316 KB | Output is correct |
13 | Correct | 26 ms | 47304 KB | Output is correct |
14 | Correct | 23 ms | 47316 KB | Output is correct |
15 | Correct | 25 ms | 47572 KB | Output is correct |
16 | Correct | 24 ms | 47440 KB | Output is correct |
17 | Correct | 23 ms | 47452 KB | Output is correct |
18 | Correct | 24 ms | 47436 KB | Output is correct |
19 | Correct | 28 ms | 47440 KB | Output is correct |
20 | Correct | 24 ms | 47492 KB | Output is correct |
21 | Correct | 23 ms | 47456 KB | Output is correct |
22 | Correct | 28 ms | 47960 KB | Output is correct |
23 | Correct | 22 ms | 47444 KB | Output is correct |
24 | Correct | 25 ms | 47464 KB | Output is correct |
25 | Correct | 23 ms | 47444 KB | Output is correct |
26 | Correct | 47 ms | 62288 KB | Output is correct |
27 | Correct | 44 ms | 61620 KB | Output is correct |
28 | Correct | 53 ms | 61512 KB | Output is correct |
29 | Correct | 63 ms | 62080 KB | Output is correct |
30 | Correct | 53 ms | 62252 KB | Output is correct |
31 | Correct | 315 ms | 80316 KB | Output is correct |
32 | Correct | 57 ms | 62220 KB | Output is correct |
33 | Correct | 51 ms | 62240 KB | Output is correct |
34 | Correct | 61 ms | 62344 KB | Output is correct |
35 | Correct | 495 ms | 89856 KB | Output is correct |
36 | Correct | 43 ms | 61012 KB | Output is correct |
37 | Correct | 62 ms | 61992 KB | Output is correct |
38 | Correct | 49 ms | 61688 KB | Output is correct |
39 | Correct | 44 ms | 61292 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 47316 KB | Output is correct |
2 | Correct | 28 ms | 47224 KB | Output is correct |
3 | Correct | 27 ms | 47360 KB | Output is correct |
4 | Correct | 25 ms | 47304 KB | Output is correct |
5 | Correct | 24 ms | 47260 KB | Output is correct |
6 | Correct | 28 ms | 47232 KB | Output is correct |
7 | Correct | 28 ms | 47352 KB | Output is correct |
8 | Correct | 26 ms | 47312 KB | Output is correct |
9 | Correct | 28 ms | 47356 KB | Output is correct |
10 | Correct | 24 ms | 47348 KB | Output is correct |
11 | Correct | 25 ms | 47248 KB | Output is correct |
12 | Correct | 24 ms | 47316 KB | Output is correct |
13 | Correct | 26 ms | 47304 KB | Output is correct |
14 | Correct | 23 ms | 47316 KB | Output is correct |
15 | Correct | 25 ms | 47572 KB | Output is correct |
16 | Correct | 24 ms | 47440 KB | Output is correct |
17 | Correct | 23 ms | 47452 KB | Output is correct |
18 | Correct | 24 ms | 47436 KB | Output is correct |
19 | Correct | 28 ms | 47440 KB | Output is correct |
20 | Correct | 24 ms | 47492 KB | Output is correct |
21 | Correct | 23 ms | 47456 KB | Output is correct |
22 | Correct | 28 ms | 47960 KB | Output is correct |
23 | Correct | 22 ms | 47444 KB | Output is correct |
24 | Correct | 25 ms | 47464 KB | Output is correct |
25 | Correct | 23 ms | 47444 KB | Output is correct |
26 | Correct | 28 ms | 47332 KB | Output is correct |
27 | Correct | 30 ms | 47288 KB | Output is correct |
28 | Correct | 31 ms | 47292 KB | Output is correct |
29 | Correct | 23 ms | 47316 KB | Output is correct |
30 | Correct | 620 ms | 423772 KB | Output is correct |
31 | Correct | 589 ms | 423704 KB | Output is correct |
32 | Correct | 619 ms | 423456 KB | Output is correct |
33 | Correct | 613 ms | 423964 KB | Output is correct |
34 | Correct | 586 ms | 424104 KB | Output is correct |
35 | Correct | 51 ms | 62260 KB | Output is correct |
36 | Correct | 27 ms | 47440 KB | Output is correct |
37 | Correct | 25 ms | 47348 KB | Output is correct |
38 | Correct | 1091 ms | 428952 KB | Output is correct |
39 | Correct | 47 ms | 62288 KB | Output is correct |
40 | Correct | 44 ms | 61620 KB | Output is correct |
41 | Correct | 53 ms | 61512 KB | Output is correct |
42 | Correct | 63 ms | 62080 KB | Output is correct |
43 | Correct | 53 ms | 62252 KB | Output is correct |
44 | Correct | 315 ms | 80316 KB | Output is correct |
45 | Correct | 57 ms | 62220 KB | Output is correct |
46 | Correct | 51 ms | 62240 KB | Output is correct |
47 | Correct | 61 ms | 62344 KB | Output is correct |
48 | Correct | 495 ms | 89856 KB | Output is correct |
49 | Correct | 43 ms | 61012 KB | Output is correct |
50 | Correct | 62 ms | 61992 KB | Output is correct |
51 | Correct | 49 ms | 61688 KB | Output is correct |
52 | Correct | 44 ms | 61292 KB | Output is correct |
53 | Correct | 706 ms | 403836 KB | Output is correct |
54 | Correct | 679 ms | 403068 KB | Output is correct |
55 | Correct | 1036 ms | 414364 KB | Output is correct |
56 | Correct | 1046 ms | 421140 KB | Output is correct |
57 | Correct | 577 ms | 424592 KB | Output is correct |
58 | Correct | 646 ms | 421236 KB | Output is correct |
59 | Correct | 636 ms | 418296 KB | Output is correct |
60 | Correct | 1171 ms | 419328 KB | Output is correct |
61 | Correct | 430 ms | 385884 KB | Output is correct |
62 | Correct | 902 ms | 414728 KB | Output is correct |
63 | Correct | 752 ms | 406092 KB | Output is correct |
64 | Correct | 551 ms | 396920 KB | Output is correct |