# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
715789 |
2023-03-28T01:03:21 Z |
cig32 |
Crossing (JOI21_crossing) |
C++17 |
|
652 ms |
22244 KB |
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
int MOD;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
string gene(string a, string b) {
string c;
for(int i=0; i<a.size(); i++) {
if(a[i] == b[i]) c += a[i];
else {
string t = "JOI";
for(int j=0; j<3; j++) {
if(a[i] != t[j] && b[i] != t[j]) c += t[j];
}
}
}
return c;
}
int random_prime(int l, int r) {
while(1) {
int x = rnd(l, r);
int c = 0;
for(int i=1; i*i<=x; i++) {
if(x%i == 0) {
c+=2;
if(i*i == x) c--;
}
}
if(c==2) return x;
}
return 1226;
}
int pre[MAXN];
int bruh;
int geometric_sequence_sum(int a, int x, int n) {
// S = ax^0+ax^1+...+ax^(n-1)
// xS = ax^1+ax^2+...+ax^n
// (x-1)S = ax^n-a
// S = a(x^n-1)/(x-1)
int s = a;
s *= pre[n] - 1;
s %= MOD;
s *= bruh;
s %= MOD;
return s;
}
int ans, n;
void add_segment(int l, int r, int v) {
ans += geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
ans %= MOD;
}
void sub_segment(int l, int r, int v) {
ans -= geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
ans += (MOD << 1);
ans %= MOD;
}
void solve(int tc) {
MOD = random_prime(5e8, 1.25 * 1e9);
cin >> n;
pre[0] = 1;
bruh = inv(2);
for(int i=1; i<=n; i++) pre[i] = (pre[i-1] * 3) % MOD;
string s[9];
cin >> s[0] >> s[1] >> s[2];
s[3] = gene(s[0], s[1]);
s[4] = gene(s[0], s[2]);
s[5] = gene(s[1], s[2]);
s[6] = gene(s[2], s[3]);
s[7] = gene(s[1], s[4]);
s[8] = gene(s[0], s[5]);
int h[9];
for(int i=0; i<9; i++) {
h[i] = 0;
for(int j=0; j<n; j++) {
h[i] = (h[i] * 3 + (s[i][j] == 'J' ? 0 : (s[i][j] == 'O' ? 1 : 2))) % MOD;
}
}
int q;
cin >> q;
string def;
cin >> def;
for(char c: def) ans = (ans * 3 + (c == 'J' ? 0 : (c == 'O' ? 1 : 2))) % MOD;
bool yes = 0;
for(int i=0; i<9; i++) yes |= (ans == h[i]);
cout << (yes ? "Yes\n" : "No\n");
set<pair<pair<int,int>,int> > ranges;
for(int i=0; i<def.size(); i++) {
int j = i;
while(j+1 < def.size() && def[j+1] == def[i]) j++;
ranges.insert({{i, j}, (def[i] == 'J' ? 0 : (def[i] == 'O' ? 1 : 2))});
i = j;
}
for(int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
--l, --r;
char c;
cin >> c;
auto it = ranges.lower_bound({{l, 0}, 0});
if(it != ranges.begin()) it--;
vector<pair<pair<int,int>,int> > to_add, to_sub;
to_add.push_back({{l, r}, (c == 'J' ? 0 : (c == 'O' ? 1 : 2))});
while(it != ranges.end() && (*it).first.first <= r) {
if((*it).first.second >= l) { // relevant
to_sub.push_back(*it);
if((*it).first.first < l) {
to_add.push_back({{(*it).first.first, l-1}, (*it).second});
}
if((*it).first.second > r) {
to_add.push_back({{r+1, (*it).first.second}, (*it).second});
}
}
it++;
}
for(auto x: to_sub) {
ranges.erase(x);
sub_segment(x.first.first, x.first.second, x.second);
}
for(auto x: to_add) {
ranges.insert(x);
add_segment(x.first.first, x.first.second, x.second);
}
bool yes = 0;
for(int i=0; i<9; i++) {
if(h[i] == ans) yes = 1;
}
cout << (yes ? "Yes\n" : "No\n");
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:25:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0; i<a.size(); i++) {
| ~^~~~~~~~~
Main.cpp: In function 'void solve(long long int)':
Main.cpp:105:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0; i<def.size(); i++) {
| ~^~~~~~~~~~~
Main.cpp:107:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while(j+1 < def.size() && def[j+1] == def[i]) j++;
| ~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
1008 KB |
Output is correct |
2 |
Correct |
220 ms |
1020 KB |
Output is correct |
3 |
Correct |
161 ms |
996 KB |
Output is correct |
4 |
Correct |
193 ms |
1040 KB |
Output is correct |
5 |
Correct |
193 ms |
1180 KB |
Output is correct |
6 |
Correct |
196 ms |
1184 KB |
Output is correct |
7 |
Correct |
195 ms |
1224 KB |
Output is correct |
8 |
Correct |
195 ms |
1172 KB |
Output is correct |
9 |
Correct |
204 ms |
1112 KB |
Output is correct |
10 |
Correct |
206 ms |
1132 KB |
Output is correct |
11 |
Correct |
210 ms |
1196 KB |
Output is correct |
12 |
Correct |
195 ms |
1096 KB |
Output is correct |
13 |
Correct |
243 ms |
1132 KB |
Output is correct |
14 |
Correct |
197 ms |
1128 KB |
Output is correct |
15 |
Correct |
208 ms |
1132 KB |
Output is correct |
16 |
Correct |
210 ms |
1100 KB |
Output is correct |
17 |
Correct |
227 ms |
1164 KB |
Output is correct |
18 |
Correct |
142 ms |
1124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
1008 KB |
Output is correct |
2 |
Correct |
220 ms |
1020 KB |
Output is correct |
3 |
Correct |
161 ms |
996 KB |
Output is correct |
4 |
Correct |
193 ms |
1040 KB |
Output is correct |
5 |
Correct |
193 ms |
1180 KB |
Output is correct |
6 |
Correct |
196 ms |
1184 KB |
Output is correct |
7 |
Correct |
195 ms |
1224 KB |
Output is correct |
8 |
Correct |
195 ms |
1172 KB |
Output is correct |
9 |
Correct |
204 ms |
1112 KB |
Output is correct |
10 |
Correct |
206 ms |
1132 KB |
Output is correct |
11 |
Correct |
210 ms |
1196 KB |
Output is correct |
12 |
Correct |
195 ms |
1096 KB |
Output is correct |
13 |
Correct |
243 ms |
1132 KB |
Output is correct |
14 |
Correct |
197 ms |
1128 KB |
Output is correct |
15 |
Correct |
208 ms |
1132 KB |
Output is correct |
16 |
Correct |
210 ms |
1100 KB |
Output is correct |
17 |
Correct |
227 ms |
1164 KB |
Output is correct |
18 |
Correct |
142 ms |
1124 KB |
Output is correct |
19 |
Correct |
516 ms |
13288 KB |
Output is correct |
20 |
Correct |
459 ms |
15552 KB |
Output is correct |
21 |
Correct |
537 ms |
18064 KB |
Output is correct |
22 |
Correct |
533 ms |
17208 KB |
Output is correct |
23 |
Correct |
357 ms |
2188 KB |
Output is correct |
24 |
Correct |
360 ms |
2196 KB |
Output is correct |
25 |
Correct |
597 ms |
22244 KB |
Output is correct |
26 |
Correct |
606 ms |
18696 KB |
Output is correct |
27 |
Correct |
405 ms |
5372 KB |
Output is correct |
28 |
Correct |
464 ms |
5368 KB |
Output is correct |
29 |
Correct |
428 ms |
5308 KB |
Output is correct |
30 |
Correct |
326 ms |
1684 KB |
Output is correct |
31 |
Correct |
420 ms |
5436 KB |
Output is correct |
32 |
Correct |
429 ms |
5732 KB |
Output is correct |
33 |
Correct |
345 ms |
2092 KB |
Output is correct |
34 |
Correct |
545 ms |
18812 KB |
Output is correct |
35 |
Correct |
588 ms |
15636 KB |
Output is correct |
36 |
Correct |
347 ms |
2192 KB |
Output is correct |
37 |
Correct |
338 ms |
2084 KB |
Output is correct |
38 |
Correct |
377 ms |
15568 KB |
Output is correct |
39 |
Correct |
393 ms |
13016 KB |
Output is correct |
40 |
Correct |
577 ms |
14392 KB |
Output is correct |
41 |
Correct |
476 ms |
18596 KB |
Output is correct |
42 |
Correct |
180 ms |
18668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
1008 KB |
Output is correct |
2 |
Correct |
220 ms |
1020 KB |
Output is correct |
3 |
Correct |
161 ms |
996 KB |
Output is correct |
4 |
Correct |
193 ms |
1040 KB |
Output is correct |
5 |
Correct |
193 ms |
1180 KB |
Output is correct |
6 |
Correct |
196 ms |
1184 KB |
Output is correct |
7 |
Correct |
195 ms |
1224 KB |
Output is correct |
8 |
Correct |
195 ms |
1172 KB |
Output is correct |
9 |
Correct |
204 ms |
1112 KB |
Output is correct |
10 |
Correct |
206 ms |
1132 KB |
Output is correct |
11 |
Correct |
210 ms |
1196 KB |
Output is correct |
12 |
Correct |
195 ms |
1096 KB |
Output is correct |
13 |
Correct |
243 ms |
1132 KB |
Output is correct |
14 |
Correct |
197 ms |
1128 KB |
Output is correct |
15 |
Correct |
208 ms |
1132 KB |
Output is correct |
16 |
Correct |
210 ms |
1100 KB |
Output is correct |
17 |
Correct |
227 ms |
1164 KB |
Output is correct |
18 |
Correct |
142 ms |
1124 KB |
Output is correct |
19 |
Correct |
213 ms |
1044 KB |
Output is correct |
20 |
Correct |
160 ms |
1104 KB |
Output is correct |
21 |
Correct |
214 ms |
1192 KB |
Output is correct |
22 |
Correct |
168 ms |
968 KB |
Output is correct |
23 |
Correct |
204 ms |
1108 KB |
Output is correct |
24 |
Correct |
211 ms |
996 KB |
Output is correct |
25 |
Correct |
198 ms |
1108 KB |
Output is correct |
26 |
Correct |
184 ms |
984 KB |
Output is correct |
27 |
Correct |
191 ms |
1136 KB |
Output is correct |
28 |
Correct |
177 ms |
1048 KB |
Output is correct |
29 |
Correct |
193 ms |
1024 KB |
Output is correct |
30 |
Correct |
180 ms |
972 KB |
Output is correct |
31 |
Correct |
196 ms |
1008 KB |
Output is correct |
32 |
Correct |
191 ms |
1104 KB |
Output is correct |
33 |
Correct |
199 ms |
1008 KB |
Output is correct |
34 |
Correct |
173 ms |
1092 KB |
Output is correct |
35 |
Correct |
200 ms |
1096 KB |
Output is correct |
36 |
Correct |
196 ms |
1040 KB |
Output is correct |
37 |
Correct |
197 ms |
1072 KB |
Output is correct |
38 |
Correct |
226 ms |
1048 KB |
Output is correct |
39 |
Correct |
192 ms |
1044 KB |
Output is correct |
40 |
Correct |
213 ms |
1120 KB |
Output is correct |
41 |
Correct |
200 ms |
1100 KB |
Output is correct |
42 |
Correct |
196 ms |
1076 KB |
Output is correct |
43 |
Correct |
189 ms |
1108 KB |
Output is correct |
44 |
Correct |
196 ms |
1000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
1008 KB |
Output is correct |
2 |
Correct |
220 ms |
1020 KB |
Output is correct |
3 |
Correct |
161 ms |
996 KB |
Output is correct |
4 |
Correct |
193 ms |
1040 KB |
Output is correct |
5 |
Correct |
193 ms |
1180 KB |
Output is correct |
6 |
Correct |
196 ms |
1184 KB |
Output is correct |
7 |
Correct |
195 ms |
1224 KB |
Output is correct |
8 |
Correct |
195 ms |
1172 KB |
Output is correct |
9 |
Correct |
204 ms |
1112 KB |
Output is correct |
10 |
Correct |
206 ms |
1132 KB |
Output is correct |
11 |
Correct |
210 ms |
1196 KB |
Output is correct |
12 |
Correct |
195 ms |
1096 KB |
Output is correct |
13 |
Correct |
243 ms |
1132 KB |
Output is correct |
14 |
Correct |
197 ms |
1128 KB |
Output is correct |
15 |
Correct |
208 ms |
1132 KB |
Output is correct |
16 |
Correct |
210 ms |
1100 KB |
Output is correct |
17 |
Correct |
227 ms |
1164 KB |
Output is correct |
18 |
Correct |
142 ms |
1124 KB |
Output is correct |
19 |
Correct |
516 ms |
13288 KB |
Output is correct |
20 |
Correct |
459 ms |
15552 KB |
Output is correct |
21 |
Correct |
537 ms |
18064 KB |
Output is correct |
22 |
Correct |
533 ms |
17208 KB |
Output is correct |
23 |
Correct |
357 ms |
2188 KB |
Output is correct |
24 |
Correct |
360 ms |
2196 KB |
Output is correct |
25 |
Correct |
597 ms |
22244 KB |
Output is correct |
26 |
Correct |
606 ms |
18696 KB |
Output is correct |
27 |
Correct |
405 ms |
5372 KB |
Output is correct |
28 |
Correct |
464 ms |
5368 KB |
Output is correct |
29 |
Correct |
428 ms |
5308 KB |
Output is correct |
30 |
Correct |
326 ms |
1684 KB |
Output is correct |
31 |
Correct |
420 ms |
5436 KB |
Output is correct |
32 |
Correct |
429 ms |
5732 KB |
Output is correct |
33 |
Correct |
345 ms |
2092 KB |
Output is correct |
34 |
Correct |
545 ms |
18812 KB |
Output is correct |
35 |
Correct |
588 ms |
15636 KB |
Output is correct |
36 |
Correct |
347 ms |
2192 KB |
Output is correct |
37 |
Correct |
338 ms |
2084 KB |
Output is correct |
38 |
Correct |
377 ms |
15568 KB |
Output is correct |
39 |
Correct |
393 ms |
13016 KB |
Output is correct |
40 |
Correct |
577 ms |
14392 KB |
Output is correct |
41 |
Correct |
476 ms |
18596 KB |
Output is correct |
42 |
Correct |
180 ms |
18668 KB |
Output is correct |
43 |
Correct |
213 ms |
1044 KB |
Output is correct |
44 |
Correct |
160 ms |
1104 KB |
Output is correct |
45 |
Correct |
214 ms |
1192 KB |
Output is correct |
46 |
Correct |
168 ms |
968 KB |
Output is correct |
47 |
Correct |
204 ms |
1108 KB |
Output is correct |
48 |
Correct |
211 ms |
996 KB |
Output is correct |
49 |
Correct |
198 ms |
1108 KB |
Output is correct |
50 |
Correct |
184 ms |
984 KB |
Output is correct |
51 |
Correct |
191 ms |
1136 KB |
Output is correct |
52 |
Correct |
177 ms |
1048 KB |
Output is correct |
53 |
Correct |
193 ms |
1024 KB |
Output is correct |
54 |
Correct |
180 ms |
972 KB |
Output is correct |
55 |
Correct |
196 ms |
1008 KB |
Output is correct |
56 |
Correct |
191 ms |
1104 KB |
Output is correct |
57 |
Correct |
199 ms |
1008 KB |
Output is correct |
58 |
Correct |
173 ms |
1092 KB |
Output is correct |
59 |
Correct |
200 ms |
1096 KB |
Output is correct |
60 |
Correct |
196 ms |
1040 KB |
Output is correct |
61 |
Correct |
197 ms |
1072 KB |
Output is correct |
62 |
Correct |
226 ms |
1048 KB |
Output is correct |
63 |
Correct |
192 ms |
1044 KB |
Output is correct |
64 |
Correct |
213 ms |
1120 KB |
Output is correct |
65 |
Correct |
200 ms |
1100 KB |
Output is correct |
66 |
Correct |
196 ms |
1076 KB |
Output is correct |
67 |
Correct |
189 ms |
1108 KB |
Output is correct |
68 |
Correct |
196 ms |
1000 KB |
Output is correct |
69 |
Correct |
450 ms |
12140 KB |
Output is correct |
70 |
Correct |
515 ms |
15556 KB |
Output is correct |
71 |
Correct |
356 ms |
2060 KB |
Output is correct |
72 |
Correct |
354 ms |
2064 KB |
Output is correct |
73 |
Correct |
380 ms |
2136 KB |
Output is correct |
74 |
Correct |
563 ms |
16380 KB |
Output is correct |
75 |
Correct |
403 ms |
2040 KB |
Output is correct |
76 |
Correct |
618 ms |
21980 KB |
Output is correct |
77 |
Correct |
592 ms |
13712 KB |
Output is correct |
78 |
Correct |
375 ms |
2068 KB |
Output is correct |
79 |
Correct |
388 ms |
2108 KB |
Output is correct |
80 |
Correct |
539 ms |
14380 KB |
Output is correct |
81 |
Correct |
375 ms |
2144 KB |
Output is correct |
82 |
Correct |
652 ms |
21984 KB |
Output is correct |
83 |
Correct |
622 ms |
17580 KB |
Output is correct |
84 |
Correct |
383 ms |
2108 KB |
Output is correct |
85 |
Correct |
382 ms |
2052 KB |
Output is correct |
86 |
Correct |
571 ms |
12784 KB |
Output is correct |
87 |
Correct |
470 ms |
5472 KB |
Output is correct |
88 |
Correct |
345 ms |
1892 KB |
Output is correct |
89 |
Correct |
450 ms |
5908 KB |
Output is correct |
90 |
Correct |
599 ms |
7104 KB |
Output is correct |
91 |
Correct |
360 ms |
1616 KB |
Output is correct |
92 |
Correct |
567 ms |
15508 KB |
Output is correct |
93 |
Correct |
363 ms |
2092 KB |
Output is correct |
94 |
Correct |
372 ms |
2096 KB |
Output is correct |
95 |
Correct |
398 ms |
2068 KB |
Output is correct |
96 |
Correct |
331 ms |
5116 KB |
Output is correct |
97 |
Correct |
395 ms |
13000 KB |
Output is correct |
98 |
Correct |
612 ms |
14156 KB |
Output is correct |
99 |
Correct |
556 ms |
18716 KB |
Output is correct |
100 |
Correct |
181 ms |
18684 KB |
Output is correct |