# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
750993 |
2023-05-30T18:10:15 Z |
sysia |
Crossing (JOI21_crossing) |
C++17 |
|
480 ms |
101008 KB |
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
void add(int &a, int b){
a += b;
if (a >= mod) a-=mod;
}
int add2(int a, int b){
add(a, b);
return a;
}
void sub(int &a, int b){
a -= b;
if (a < 0) a += mod;
}
int mul(int a, int b){
return (a*b)%mod;
}
T f(T a, T b){
return T{add2(a.first, b.first), add2(a.second, b.second)};
}
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int p(int a, int b){
return a + rng()%(b-a+1);
}
/*
struct Tree{
vector<T>tab;
int size = 1;
Tree(int n, string&s){
while (size < n) size*=2;
tab.assign(2*size, {0, 0});
}
void update(int x, T v){
x += size;
tab[x] = v;
while (x){
x/=2;
tab[x] = f(tab[2*x], tab[2*x+1]);
}
}
T query(int l, int r){
T ans = {0, 0};
for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
if (!(l&1)) ans = f(ans, tab[l+1]);
if (r&1) ans = f(ans, tab[r-1]);
}
return ans;
}
};
*/
set<vector<int>>now;
vector<int>A, B, C;
int change(char c){
if (c == 'J') return 0;
else if (c == 'O') return 1;
return 2;
}
void gen(string s, vector<int>&a){
for (auto c: s){
a.emplace_back(change(c));
}
}
vector<int> merge(vector<int>&a, vector<int>&b){
vector<int>ret;
for (int i = 0; i<(int)a.size(); i++){
ret.emplace_back((2*a[i] + 2*b[i])%3);
}
return ret;
}
struct Q{
int l, r, c;
T h;
Q(){}
Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
bool operator <(const Q&he) const {
return l < he.l;
}
};
void rec(vector<int>s){
if (now.find(s) != now.end()) return;
now.insert(s);
for (auto t: {A, B, C}){
rec(merge(s, t));
}
}
int sub2(int a, int b){
sub(a, b);
return a;
}
T fsub(T a, T b){
return {sub2(a.first, b.first), sub2(a.second, b.second)};
}
void solve(){
int n; cin >> n;
string a, b, c; cin >> a >> b >> c;
gen(a, A);
gen(b, B);
gen(c, C);
for (auto s: {A, B, C}) rec(s);
assert((int)now.size() <= 9);
vector<T>Hash;
int b1 = p(1, mod-1), b2 = p(1, mod-1);
T p = {1, 1};
for (auto vt: now){
T H = {0, 0};
// debug(vt);
p = {1, 1};
for (auto ch: vt){
H = f(H, {mul(ch, p.first), mul(ch, p.second)});
p = {mul(p.first, b1), mul(p.second, b2)};
// debug(H);
}
Hash.emplace_back(H);
}
int q; cin >> q >> a;
A.clear(); gen(a, A);
set<Q>blocks;
int begin = 0;
T sum = {0, 0}, all = {0, 0};
p = {1, 1};
for (int i = 0; i<n; i++){
if (i && A[i] != A[i-1]){
blocks.insert({begin, i-1, sum, A[i-1]});
begin = i;
sum = {0, 0};
}
sum = f(sum, {mul(A[i], p.first), mul(A[i], p.second)});
all = f(all, {mul(A[i], p.first), mul(A[i], p.second)});
p = {mul(p.first, b1), mul(p.second, b2)};
}
blocks.insert({begin, n-1, sum, A.back()});
// for (auto [l, r, h, c]: blocks){
// debug(l, r, h, c);
// }
auto answer = [&](){
for (auto x: Hash){
if (x == all){
cout << "Yes\n";
return;
}
}
cout << "No\n";
};
debug(all);
answer();
vector<int>power1(n+1), power2(n+1);
vector<int>pref1(n+1), pref2(n+1);
power1[0] = power2[0] = 1;
pref1[0] = pref2[0] = 1;
for (int i = 1; i<=n; i++){
power1[i] = mul(power1[i-1], b1);
power2[i] = mul(power2[i-1], b2);
pref1[i] = add2(pref1[i-1], power1[i]);
pref2[i] = add2(pref2[i-1], power2[i]);
}
auto get_sum = [&](int l, int r, int v)->T {
if (r < l) return T{0ll, 0ll};
T ret;
ret.first = mul(power1[l], mul(v, pref1[r-l]));
ret.second = mul(power2[l], mul(v, pref2[r-l]));
return ret;
};
while (q--){
int l, r; char d; cin >> l >> r >> d;
--l;--r;
debug(l, r, d);
int what = change(d);
auto wrr = prev(blocks.upper_bound({l, -oo, {-oo, -oo}, -oo}));
vector<Q>change;
vector<int>fix;
for (auto it = wrr; it != blocks.end() && it->l <= r; it++){
auto [ll, rr, val, hh] = *it;
fix.emplace_back(ll);
// debug(ll, rr, val, hh);
if (ll >= l && rr <= r){
all = fsub(all, hh);
} else {
//at most two such intervals
bool sub = 0;
if (ll < l){
change.emplace_back(ll, l-1, get_sum(ll, l-1, val), val);
all = fsub(all, get_sum(l, min(rr, r), val));
sub = 1;
}
if (rr > r){
change.emplace_back(r+1, rr, get_sum(r+1, rr, val), val);
if (!sub){
all = fsub(all, get_sum(max(ll, l), r, val));
}
}
}
}
debug(all);
change.emplace_back(l, r, get_sum(l, r, what), what);
for (auto x: fix){
blocks.erase(blocks.lower_bound({x, -oo, {-oo, -oo}, -oo}));
}
all = f(all, get_sum(l, r, what));
for (auto x: change) {
blocks.insert(x);
}
// for (auto [l, r, val, hh]: blocks){
// debug(l, r, val, hh);
// }
debug(all);
answer();
}
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
Compilation message
Main.cpp: In constructor 'Q::Q(long long int, long long int, T, long long int)':
Main.cpp:114:7: warning: 'Q::h' will be initialized after [-Wreorder]
114 | T h;
| ^
Main.cpp:113:15: warning: 'long long int Q::c' [-Wreorder]
113 | int l, r, c;
| ^
Main.cpp:116:5: warning: when initialized here [-Wreorder]
116 | Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
804 KB |
Output is correct |
2 |
Correct |
159 ms |
816 KB |
Output is correct |
3 |
Correct |
124 ms |
904 KB |
Output is correct |
4 |
Correct |
150 ms |
860 KB |
Output is correct |
5 |
Correct |
127 ms |
844 KB |
Output is correct |
6 |
Correct |
131 ms |
868 KB |
Output is correct |
7 |
Correct |
135 ms |
952 KB |
Output is correct |
8 |
Correct |
133 ms |
840 KB |
Output is correct |
9 |
Correct |
163 ms |
828 KB |
Output is correct |
10 |
Correct |
138 ms |
868 KB |
Output is correct |
11 |
Correct |
145 ms |
996 KB |
Output is correct |
12 |
Correct |
139 ms |
936 KB |
Output is correct |
13 |
Correct |
155 ms |
832 KB |
Output is correct |
14 |
Correct |
137 ms |
936 KB |
Output is correct |
15 |
Correct |
137 ms |
892 KB |
Output is correct |
16 |
Correct |
137 ms |
928 KB |
Output is correct |
17 |
Correct |
146 ms |
924 KB |
Output is correct |
18 |
Correct |
115 ms |
928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
804 KB |
Output is correct |
2 |
Correct |
159 ms |
816 KB |
Output is correct |
3 |
Correct |
124 ms |
904 KB |
Output is correct |
4 |
Correct |
150 ms |
860 KB |
Output is correct |
5 |
Correct |
127 ms |
844 KB |
Output is correct |
6 |
Correct |
131 ms |
868 KB |
Output is correct |
7 |
Correct |
135 ms |
952 KB |
Output is correct |
8 |
Correct |
133 ms |
840 KB |
Output is correct |
9 |
Correct |
163 ms |
828 KB |
Output is correct |
10 |
Correct |
138 ms |
868 KB |
Output is correct |
11 |
Correct |
145 ms |
996 KB |
Output is correct |
12 |
Correct |
139 ms |
936 KB |
Output is correct |
13 |
Correct |
155 ms |
832 KB |
Output is correct |
14 |
Correct |
137 ms |
936 KB |
Output is correct |
15 |
Correct |
137 ms |
892 KB |
Output is correct |
16 |
Correct |
137 ms |
928 KB |
Output is correct |
17 |
Correct |
146 ms |
924 KB |
Output is correct |
18 |
Correct |
115 ms |
928 KB |
Output is correct |
19 |
Correct |
302 ms |
24940 KB |
Output is correct |
20 |
Correct |
266 ms |
26344 KB |
Output is correct |
21 |
Correct |
380 ms |
25040 KB |
Output is correct |
22 |
Correct |
378 ms |
23240 KB |
Output is correct |
23 |
Correct |
206 ms |
2252 KB |
Output is correct |
24 |
Correct |
201 ms |
2176 KB |
Output is correct |
25 |
Correct |
375 ms |
27468 KB |
Output is correct |
26 |
Correct |
434 ms |
26956 KB |
Output is correct |
27 |
Correct |
237 ms |
24928 KB |
Output is correct |
28 |
Correct |
247 ms |
24928 KB |
Output is correct |
29 |
Correct |
229 ms |
24344 KB |
Output is correct |
30 |
Correct |
180 ms |
1868 KB |
Output is correct |
31 |
Correct |
272 ms |
24928 KB |
Output is correct |
32 |
Correct |
263 ms |
22968 KB |
Output is correct |
33 |
Correct |
218 ms |
2096 KB |
Output is correct |
34 |
Correct |
315 ms |
26960 KB |
Output is correct |
35 |
Correct |
391 ms |
20608 KB |
Output is correct |
36 |
Correct |
211 ms |
2180 KB |
Output is correct |
37 |
Correct |
206 ms |
2172 KB |
Output is correct |
38 |
Correct |
224 ms |
26484 KB |
Output is correct |
39 |
Correct |
271 ms |
24876 KB |
Output is correct |
40 |
Correct |
373 ms |
18216 KB |
Output is correct |
41 |
Correct |
303 ms |
26880 KB |
Output is correct |
42 |
Correct |
129 ms |
26960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
804 KB |
Output is correct |
2 |
Correct |
159 ms |
816 KB |
Output is correct |
3 |
Correct |
124 ms |
904 KB |
Output is correct |
4 |
Correct |
150 ms |
860 KB |
Output is correct |
5 |
Correct |
127 ms |
844 KB |
Output is correct |
6 |
Correct |
131 ms |
868 KB |
Output is correct |
7 |
Correct |
135 ms |
952 KB |
Output is correct |
8 |
Correct |
133 ms |
840 KB |
Output is correct |
9 |
Correct |
163 ms |
828 KB |
Output is correct |
10 |
Correct |
138 ms |
868 KB |
Output is correct |
11 |
Correct |
145 ms |
996 KB |
Output is correct |
12 |
Correct |
139 ms |
936 KB |
Output is correct |
13 |
Correct |
155 ms |
832 KB |
Output is correct |
14 |
Correct |
137 ms |
936 KB |
Output is correct |
15 |
Correct |
137 ms |
892 KB |
Output is correct |
16 |
Correct |
137 ms |
928 KB |
Output is correct |
17 |
Correct |
146 ms |
924 KB |
Output is correct |
18 |
Correct |
115 ms |
928 KB |
Output is correct |
19 |
Correct |
153 ms |
908 KB |
Output is correct |
20 |
Correct |
133 ms |
872 KB |
Output is correct |
21 |
Correct |
132 ms |
1028 KB |
Output is correct |
22 |
Correct |
122 ms |
860 KB |
Output is correct |
23 |
Correct |
142 ms |
844 KB |
Output is correct |
24 |
Correct |
149 ms |
1008 KB |
Output is correct |
25 |
Correct |
141 ms |
860 KB |
Output is correct |
26 |
Correct |
131 ms |
840 KB |
Output is correct |
27 |
Correct |
135 ms |
812 KB |
Output is correct |
28 |
Correct |
126 ms |
872 KB |
Output is correct |
29 |
Correct |
136 ms |
928 KB |
Output is correct |
30 |
Correct |
141 ms |
904 KB |
Output is correct |
31 |
Correct |
151 ms |
840 KB |
Output is correct |
32 |
Correct |
133 ms |
872 KB |
Output is correct |
33 |
Correct |
142 ms |
948 KB |
Output is correct |
34 |
Correct |
148 ms |
864 KB |
Output is correct |
35 |
Correct |
139 ms |
864 KB |
Output is correct |
36 |
Correct |
142 ms |
916 KB |
Output is correct |
37 |
Correct |
151 ms |
964 KB |
Output is correct |
38 |
Correct |
136 ms |
948 KB |
Output is correct |
39 |
Correct |
140 ms |
952 KB |
Output is correct |
40 |
Correct |
156 ms |
972 KB |
Output is correct |
41 |
Correct |
137 ms |
896 KB |
Output is correct |
42 |
Correct |
158 ms |
1068 KB |
Output is correct |
43 |
Correct |
134 ms |
944 KB |
Output is correct |
44 |
Correct |
140 ms |
956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
804 KB |
Output is correct |
2 |
Correct |
159 ms |
816 KB |
Output is correct |
3 |
Correct |
124 ms |
904 KB |
Output is correct |
4 |
Correct |
150 ms |
860 KB |
Output is correct |
5 |
Correct |
127 ms |
844 KB |
Output is correct |
6 |
Correct |
131 ms |
868 KB |
Output is correct |
7 |
Correct |
135 ms |
952 KB |
Output is correct |
8 |
Correct |
133 ms |
840 KB |
Output is correct |
9 |
Correct |
163 ms |
828 KB |
Output is correct |
10 |
Correct |
138 ms |
868 KB |
Output is correct |
11 |
Correct |
145 ms |
996 KB |
Output is correct |
12 |
Correct |
139 ms |
936 KB |
Output is correct |
13 |
Correct |
155 ms |
832 KB |
Output is correct |
14 |
Correct |
137 ms |
936 KB |
Output is correct |
15 |
Correct |
137 ms |
892 KB |
Output is correct |
16 |
Correct |
137 ms |
928 KB |
Output is correct |
17 |
Correct |
146 ms |
924 KB |
Output is correct |
18 |
Correct |
115 ms |
928 KB |
Output is correct |
19 |
Correct |
302 ms |
24940 KB |
Output is correct |
20 |
Correct |
266 ms |
26344 KB |
Output is correct |
21 |
Correct |
380 ms |
25040 KB |
Output is correct |
22 |
Correct |
378 ms |
23240 KB |
Output is correct |
23 |
Correct |
206 ms |
2252 KB |
Output is correct |
24 |
Correct |
201 ms |
2176 KB |
Output is correct |
25 |
Correct |
375 ms |
27468 KB |
Output is correct |
26 |
Correct |
434 ms |
26956 KB |
Output is correct |
27 |
Correct |
237 ms |
24928 KB |
Output is correct |
28 |
Correct |
247 ms |
24928 KB |
Output is correct |
29 |
Correct |
229 ms |
24344 KB |
Output is correct |
30 |
Correct |
180 ms |
1868 KB |
Output is correct |
31 |
Correct |
272 ms |
24928 KB |
Output is correct |
32 |
Correct |
263 ms |
22968 KB |
Output is correct |
33 |
Correct |
218 ms |
2096 KB |
Output is correct |
34 |
Correct |
315 ms |
26960 KB |
Output is correct |
35 |
Correct |
391 ms |
20608 KB |
Output is correct |
36 |
Correct |
211 ms |
2180 KB |
Output is correct |
37 |
Correct |
206 ms |
2172 KB |
Output is correct |
38 |
Correct |
224 ms |
26484 KB |
Output is correct |
39 |
Correct |
271 ms |
24876 KB |
Output is correct |
40 |
Correct |
373 ms |
18216 KB |
Output is correct |
41 |
Correct |
303 ms |
26880 KB |
Output is correct |
42 |
Correct |
129 ms |
26960 KB |
Output is correct |
43 |
Correct |
153 ms |
908 KB |
Output is correct |
44 |
Correct |
133 ms |
872 KB |
Output is correct |
45 |
Correct |
132 ms |
1028 KB |
Output is correct |
46 |
Correct |
122 ms |
860 KB |
Output is correct |
47 |
Correct |
142 ms |
844 KB |
Output is correct |
48 |
Correct |
149 ms |
1008 KB |
Output is correct |
49 |
Correct |
141 ms |
860 KB |
Output is correct |
50 |
Correct |
131 ms |
840 KB |
Output is correct |
51 |
Correct |
135 ms |
812 KB |
Output is correct |
52 |
Correct |
126 ms |
872 KB |
Output is correct |
53 |
Correct |
136 ms |
928 KB |
Output is correct |
54 |
Correct |
141 ms |
904 KB |
Output is correct |
55 |
Correct |
151 ms |
840 KB |
Output is correct |
56 |
Correct |
133 ms |
872 KB |
Output is correct |
57 |
Correct |
142 ms |
948 KB |
Output is correct |
58 |
Correct |
148 ms |
864 KB |
Output is correct |
59 |
Correct |
139 ms |
864 KB |
Output is correct |
60 |
Correct |
142 ms |
916 KB |
Output is correct |
61 |
Correct |
151 ms |
964 KB |
Output is correct |
62 |
Correct |
136 ms |
948 KB |
Output is correct |
63 |
Correct |
140 ms |
952 KB |
Output is correct |
64 |
Correct |
156 ms |
972 KB |
Output is correct |
65 |
Correct |
137 ms |
896 KB |
Output is correct |
66 |
Correct |
158 ms |
1068 KB |
Output is correct |
67 |
Correct |
134 ms |
944 KB |
Output is correct |
68 |
Correct |
140 ms |
956 KB |
Output is correct |
69 |
Correct |
336 ms |
86012 KB |
Output is correct |
70 |
Correct |
337 ms |
100196 KB |
Output is correct |
71 |
Correct |
209 ms |
3044 KB |
Output is correct |
72 |
Correct |
207 ms |
3044 KB |
Output is correct |
73 |
Correct |
205 ms |
3016 KB |
Output is correct |
74 |
Correct |
431 ms |
37300 KB |
Output is correct |
75 |
Correct |
205 ms |
2956 KB |
Output is correct |
76 |
Correct |
424 ms |
43908 KB |
Output is correct |
77 |
Correct |
346 ms |
37400 KB |
Output is correct |
78 |
Correct |
202 ms |
2984 KB |
Output is correct |
79 |
Correct |
215 ms |
3032 KB |
Output is correct |
80 |
Correct |
350 ms |
72184 KB |
Output is correct |
81 |
Correct |
201 ms |
5736 KB |
Output is correct |
82 |
Correct |
480 ms |
100260 KB |
Output is correct |
83 |
Correct |
427 ms |
94776 KB |
Output is correct |
84 |
Correct |
203 ms |
5748 KB |
Output is correct |
85 |
Correct |
210 ms |
5816 KB |
Output is correct |
86 |
Correct |
326 ms |
76716 KB |
Output is correct |
87 |
Correct |
369 ms |
100276 KB |
Output is correct |
88 |
Correct |
197 ms |
5928 KB |
Output is correct |
89 |
Correct |
351 ms |
89804 KB |
Output is correct |
90 |
Correct |
368 ms |
100292 KB |
Output is correct |
91 |
Correct |
205 ms |
5748 KB |
Output is correct |
92 |
Correct |
437 ms |
75620 KB |
Output is correct |
93 |
Correct |
210 ms |
5808 KB |
Output is correct |
94 |
Correct |
224 ms |
5764 KB |
Output is correct |
95 |
Correct |
206 ms |
5844 KB |
Output is correct |
96 |
Correct |
173 ms |
24912 KB |
Output is correct |
97 |
Correct |
356 ms |
100188 KB |
Output is correct |
98 |
Correct |
420 ms |
66048 KB |
Output is correct |
99 |
Correct |
337 ms |
101008 KB |
Output is correct |
100 |
Correct |
196 ms |
100960 KB |
Output is correct |