oj.uz

Submission #898058

# Submission time Handle Problem Language Result Execution time Memory
898058 2024-01-04T09:27:05 Z vjudge1 Misspelling (JOI22_misspelling) C++17
100 / 100
 400 ms 188000 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define str string
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define setpr(x) cout << fixed << setprecision(x) 
#define endl '\n'
 
const int inf = INT_MAX;
const ld eps = 1e-9 , pi = acos(-1.0);
const ll mod = 1e9 + 7; // 998244353;
const int dx[4]{1 , 0 , -1 , 0} , dy[4]{0 , 1 , 0 , -1};

/*
    T_ai <= T_bi --> 
    ai < bi --> S_(ai + 1 , bi) <= S_(ai , bi - 1)
    ai > bi --> S_(bi + 1 , ai) >= S_(bi , ai - 1)
*/

void solution(){
    int n , m; cin >> n >> m;
    vector<vector<int>> kat(n + 1) , kic(n + 1) , dp(n + 1 , vector<int>(26));
	for(int i = 0 ; i < 26 ; i ++) dp[n][i] = 1;
    set<int> kat_u , kic_u;
    vector<int> kat_sm(26) , kic_sm(26);
    for(int i = 0 , ai , bi ; i < m ; i ++){
        cin >> ai >> bi;
        if(ai < bi) kat[ai].pb(bi);
		else if(ai != bi) kic[bi].pb(ai);
    }
	for(int i = n - 1 ; i >= 1 ; i --){
		kat_u.insert(i + 1); kic_u.insert(i + 1);
		for(int j = 0 ; j < 26 ; j ++){
			kat_sm[j] += dp[i + 1][j];
		}
        for(int j = 0 ; j < 26 ; j ++){
			kic_sm[j] += dp[i + 1][j];
		}
		for(auto x : kat[i]){
			auto it = kat_u.lower_bound(i + 1);
			while(it != kat_u.end() && (*it) <= x){
				for(int j = 0 ; j < 26 ; j ++) kat_sm[j] -= dp[(*it)][j]; it = kat_u.erase(it);
			}
		}
		for (auto x : kic[i]) {
			auto it = kic_u.lower_bound(i + 1);
			while(it != kic_u.end() && (*it) <= x){
				for(int j = 0 ; j < 26 ; j ++) kic_sm[j] -= dp[(*it)][j]; it = kic_u.erase(it);
			}
		}
		int h = 0 , p = 0;
		for(int j = 0 ; j < 26 ; j ++){
			dp[i][j] += h;
            dp[i][26 - j - 1] += p;
			h += kic_sm[j];
            p += kat_sm[26 - j - 1];
		}
		for(int j = 0 ; j < 26 ; j ++) dp[i][j] ++ , dp[i][j] %= mod;
	}
	int h = 0;
	for (int j = 0 ; j < 26 ; j ++) h += dp[1][j];
	cout << h % mod;
}  
 
signed main(){
    IOS;
    int t = 1; // cin >> t;
    while(t --) solution();
}

Compilation message

misspelling.cpp: In function 'void solution()':
misspelling.cpp:52:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   52 |     for(int j = 0 ; j < 26 ; j ++) kat_sm[j] -= dp[(*it)][j]; it = kat_u.erase(it);
      |     ^~~
misspelling.cpp:52:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   52 |     for(int j = 0 ; j < 26 ; j ++) kat_sm[j] -= dp[(*it)][j]; it = kat_u.erase(it);
      |                                                               ^~
misspelling.cpp:58:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |     for(int j = 0 ; j < 26 ; j ++) kic_sm[j] -= dp[(*it)][j]; it = kic_u.erase(it);
      |     ^~~
misspelling.cpp:58:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |     for(int j = 0 ; j < 26 ; j ++) kic_sm[j] -= dp[(*it)][j]; it = kic_u.erase(it);
      |                                                               ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 416 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 235 ms 160780 KB Output is correct
6 Correct 231 ms 160852 KB Output is correct
7 Correct 233 ms 160924 KB Output is correct
8 Correct 242 ms 161144 KB Output is correct
9 Correct 236 ms 160952 KB Output is correct
10 Correct 9 ms 6748 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 335 ms 161260 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 9 ms 6748 KB Output is correct
27 Correct 10 ms 7452 KB Output is correct
28 Correct 11 ms 7512 KB Output is correct
29 Correct 11 ms 6748 KB Output is correct
30 Correct 10 ms 7000 KB Output is correct
31 Correct 80 ms 12644 KB Output is correct
32 Correct 9 ms 6748 KB Output is correct
33 Correct 9 ms 6896 KB Output is correct
34 Correct 11 ms 6748 KB Output is correct
35 Correct 98 ms 13204 KB Output is correct
36 Correct 11 ms 8028 KB Output is correct
37 Correct 11 ms 6492 KB Output is correct
38 Correct 9 ms 6492 KB Output is correct
39 Correct 9 ms 6236 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 416 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 235 ms 160780 KB Output is correct
31 Correct 231 ms 160852 KB Output is correct
32 Correct 233 ms 160924 KB Output is correct
33 Correct 242 ms 161144 KB Output is correct
34 Correct 236 ms 160952 KB Output is correct
35 Correct 9 ms 6748 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 335 ms 161260 KB Output is correct
39 Correct 9 ms 6748 KB Output is correct
40 Correct 10 ms 7452 KB Output is correct
41 Correct 11 ms 7512 KB Output is correct
42 Correct 11 ms 6748 KB Output is correct
43 Correct 10 ms 7000 KB Output is correct
44 Correct 80 ms 12644 KB Output is correct
45 Correct 9 ms 6748 KB Output is correct
46 Correct 9 ms 6896 KB Output is correct
47 Correct 11 ms 6748 KB Output is correct
48 Correct 98 ms 13204 KB Output is correct
49 Correct 11 ms 8028 KB Output is correct
50 Correct 11 ms 6492 KB Output is correct
51 Correct 9 ms 6492 KB Output is correct
52 Correct 9 ms 6236 KB Output is correct
53 Correct 227 ms 155216 KB Output is correct
54 Correct 282 ms 176376 KB Output is correct
55 Correct 331 ms 161484 KB Output is correct
56 Correct 400 ms 165108 KB Output is correct
57 Correct 252 ms 164504 KB Output is correct
58 Correct 274 ms 164508 KB Output is correct
59 Correct 244 ms 164284 KB Output is correct
60 Correct 376 ms 160848 KB Output is correct
61 Correct 347 ms 188000 KB Output is correct
62 Correct 343 ms 157724 KB Output is correct
63 Correct 283 ms 154192 KB Output is correct
64 Correct 262 ms 150108 KB Output is correct