# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
689837 | 2023-01-29T13:47:18 Z | fcmalkcin | Misspelling (JOI22_misspelling) | C++17 | 993 ms | 422676 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]; // dp[i][t] số lượng xâu mà si = t và si != si-1 // bao ham loai tru lay tat ca kha nang co the (cnt[t] voi t->1->26) tru di tat ca cac truong hop sai la cac dp[j][k] voi (j > pre va k > t) hoac (j < pre1 va k < t) 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=1;t<=26;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=26;t>=1;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 | 27 ms | 47316 KB | Output is correct |
2 | Correct | 24 ms | 47312 KB | Output is correct |
3 | Correct | 22 ms | 47272 KB | Output is correct |
4 | Correct | 27 ms | 47284 KB | Output is correct |
5 | Correct | 27 ms | 47336 KB | Output is correct |
6 | Correct | 25 ms | 47276 KB | Output is correct |
7 | Correct | 22 ms | 47312 KB | Output is correct |
8 | Correct | 22 ms | 47316 KB | Output is correct |
9 | Correct | 23 ms | 47272 KB | Output is correct |
10 | Correct | 25 ms | 47320 KB | Output is correct |
11 | Correct | 26 ms | 47272 KB | Output is correct |
12 | Correct | 28 ms | 47332 KB | Output is correct |
13 | Correct | 24 ms | 47224 KB | Output is correct |
14 | Correct | 22 ms | 47340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 47316 KB | Output is correct |
2 | Correct | 24 ms | 47312 KB | Output is correct |
3 | Correct | 22 ms | 47272 KB | Output is correct |
4 | Correct | 27 ms | 47284 KB | Output is correct |
5 | Correct | 27 ms | 47336 KB | Output is correct |
6 | Correct | 25 ms | 47276 KB | Output is correct |
7 | Correct | 22 ms | 47312 KB | Output is correct |
8 | Correct | 22 ms | 47316 KB | Output is correct |
9 | Correct | 23 ms | 47272 KB | Output is correct |
10 | Correct | 25 ms | 47320 KB | Output is correct |
11 | Correct | 26 ms | 47272 KB | Output is correct |
12 | Correct | 28 ms | 47332 KB | Output is correct |
13 | Correct | 24 ms | 47224 KB | Output is correct |
14 | Correct | 22 ms | 47340 KB | Output is correct |
15 | Correct | 33 ms | 47368 KB | Output is correct |
16 | Correct | 31 ms | 47444 KB | Output is correct |
17 | Correct | 23 ms | 47468 KB | Output is correct |
18 | Correct | 27 ms | 47444 KB | Output is correct |
19 | Correct | 23 ms | 47444 KB | Output is correct |
20 | Correct | 23 ms | 47492 KB | Output is correct |
21 | Correct | 22 ms | 47444 KB | Output is correct |
22 | Correct | 30 ms | 47936 KB | Output is correct |
23 | Correct | 25 ms | 47392 KB | Output is correct |
24 | Correct | 25 ms | 47444 KB | Output is correct |
25 | Correct | 24 ms | 47392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 47308 KB | Output is correct |
2 | Correct | 25 ms | 47224 KB | Output is correct |
3 | Correct | 24 ms | 47316 KB | Output is correct |
4 | Correct | 23 ms | 47316 KB | Output is correct |
5 | Correct | 553 ms | 418296 KB | Output is correct |
6 | Correct | 557 ms | 418252 KB | Output is correct |
7 | Correct | 533 ms | 418192 KB | Output is correct |
8 | Correct | 566 ms | 418216 KB | Output is correct |
9 | Correct | 550 ms | 418256 KB | Output is correct |
10 | Correct | 46 ms | 62164 KB | Output is correct |
11 | Correct | 25 ms | 47444 KB | Output is correct |
12 | Correct | 24 ms | 47316 KB | Output is correct |
13 | Correct | 993 ms | 422676 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 47316 KB | Output is correct |
2 | Correct | 24 ms | 47312 KB | Output is correct |
3 | Correct | 22 ms | 47272 KB | Output is correct |
4 | Correct | 27 ms | 47284 KB | Output is correct |
5 | Correct | 27 ms | 47336 KB | Output is correct |
6 | Correct | 25 ms | 47276 KB | Output is correct |
7 | Correct | 22 ms | 47312 KB | Output is correct |
8 | Correct | 22 ms | 47316 KB | Output is correct |
9 | Correct | 23 ms | 47272 KB | Output is correct |
10 | Correct | 25 ms | 47320 KB | Output is correct |
11 | Correct | 26 ms | 47272 KB | Output is correct |
12 | Correct | 28 ms | 47332 KB | Output is correct |
13 | Correct | 24 ms | 47224 KB | Output is correct |
14 | Correct | 22 ms | 47340 KB | Output is correct |
15 | Correct | 33 ms | 47368 KB | Output is correct |
16 | Correct | 31 ms | 47444 KB | Output is correct |
17 | Correct | 23 ms | 47468 KB | Output is correct |
18 | Correct | 27 ms | 47444 KB | Output is correct |
19 | Correct | 23 ms | 47444 KB | Output is correct |
20 | Correct | 23 ms | 47492 KB | Output is correct |
21 | Correct | 22 ms | 47444 KB | Output is correct |
22 | Correct | 30 ms | 47936 KB | Output is correct |
23 | Correct | 25 ms | 47392 KB | Output is correct |
24 | Correct | 25 ms | 47444 KB | Output is correct |
25 | Correct | 24 ms | 47392 KB | Output is correct |
26 | Correct | 53 ms | 62168 KB | Output is correct |
27 | Correct | 43 ms | 61476 KB | Output is correct |
28 | Correct | 45 ms | 61364 KB | Output is correct |
29 | Correct | 50 ms | 62008 KB | Output is correct |
30 | Correct | 49 ms | 62024 KB | Output is correct |
31 | Correct | 261 ms | 76304 KB | Output is correct |
32 | Correct | 46 ms | 62108 KB | Output is correct |
33 | Correct | 46 ms | 62096 KB | Output is correct |
34 | Correct | 56 ms | 62156 KB | Output is correct |
35 | Correct | 513 ms | 86676 KB | Output is correct |
36 | Correct | 47 ms | 61000 KB | Output is correct |
37 | Correct | 48 ms | 61824 KB | Output is correct |
38 | Correct | 45 ms | 61552 KB | Output is correct |
39 | Correct | 44 ms | 61284 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 47316 KB | Output is correct |
2 | Correct | 24 ms | 47312 KB | Output is correct |
3 | Correct | 22 ms | 47272 KB | Output is correct |
4 | Correct | 27 ms | 47284 KB | Output is correct |
5 | Correct | 27 ms | 47336 KB | Output is correct |
6 | Correct | 25 ms | 47276 KB | Output is correct |
7 | Correct | 22 ms | 47312 KB | Output is correct |
8 | Correct | 22 ms | 47316 KB | Output is correct |
9 | Correct | 23 ms | 47272 KB | Output is correct |
10 | Correct | 25 ms | 47320 KB | Output is correct |
11 | Correct | 26 ms | 47272 KB | Output is correct |
12 | Correct | 28 ms | 47332 KB | Output is correct |
13 | Correct | 24 ms | 47224 KB | Output is correct |
14 | Correct | 22 ms | 47340 KB | Output is correct |
15 | Correct | 33 ms | 47368 KB | Output is correct |
16 | Correct | 31 ms | 47444 KB | Output is correct |
17 | Correct | 23 ms | 47468 KB | Output is correct |
18 | Correct | 27 ms | 47444 KB | Output is correct |
19 | Correct | 23 ms | 47444 KB | Output is correct |
20 | Correct | 23 ms | 47492 KB | Output is correct |
21 | Correct | 22 ms | 47444 KB | Output is correct |
22 | Correct | 30 ms | 47936 KB | Output is correct |
23 | Correct | 25 ms | 47392 KB | Output is correct |
24 | Correct | 25 ms | 47444 KB | Output is correct |
25 | Correct | 24 ms | 47392 KB | Output is correct |
26 | Correct | 33 ms | 47308 KB | Output is correct |
27 | Correct | 25 ms | 47224 KB | Output is correct |
28 | Correct | 24 ms | 47316 KB | Output is correct |
29 | Correct | 23 ms | 47316 KB | Output is correct |
30 | Correct | 553 ms | 418296 KB | Output is correct |
31 | Correct | 557 ms | 418252 KB | Output is correct |
32 | Correct | 533 ms | 418192 KB | Output is correct |
33 | Correct | 566 ms | 418216 KB | Output is correct |
34 | Correct | 550 ms | 418256 KB | Output is correct |
35 | Correct | 46 ms | 62164 KB | Output is correct |
36 | Correct | 25 ms | 47444 KB | Output is correct |
37 | Correct | 24 ms | 47316 KB | Output is correct |
38 | Correct | 993 ms | 422676 KB | Output is correct |
39 | Correct | 53 ms | 62168 KB | Output is correct |
40 | Correct | 43 ms | 61476 KB | Output is correct |
41 | Correct | 45 ms | 61364 KB | Output is correct |
42 | Correct | 50 ms | 62008 KB | Output is correct |
43 | Correct | 49 ms | 62024 KB | Output is correct |
44 | Correct | 261 ms | 76304 KB | Output is correct |
45 | Correct | 46 ms | 62108 KB | Output is correct |
46 | Correct | 46 ms | 62096 KB | Output is correct |
47 | Correct | 56 ms | 62156 KB | Output is correct |
48 | Correct | 513 ms | 86676 KB | Output is correct |
49 | Correct | 47 ms | 61000 KB | Output is correct |
50 | Correct | 48 ms | 61824 KB | Output is correct |
51 | Correct | 45 ms | 61552 KB | Output is correct |
52 | Correct | 44 ms | 61284 KB | Output is correct |
53 | Correct | 616 ms | 400716 KB | Output is correct |
54 | Correct | 602 ms | 399968 KB | Output is correct |
55 | Correct | 907 ms | 414292 KB | Output is correct |
56 | Correct | 880 ms | 414380 KB | Output is correct |
57 | Correct | 578 ms | 418252 KB | Output is correct |
58 | Correct | 533 ms | 418188 KB | Output is correct |
59 | Correct | 556 ms | 418352 KB | Output is correct |
60 | Correct | 993 ms | 417108 KB | Output is correct |
61 | Correct | 401 ms | 386024 KB | Output is correct |
62 | Correct | 833 ms | 409948 KB | Output is correct |
63 | Correct | 674 ms | 402832 KB | Output is correct |
64 | Correct | 530 ms | 395228 KB | Output is correct |