# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
502429 |
2022-01-06T01:00:17 Z |
cig32 |
Crossing (JOI21_crossing) |
C++17 |
|
2405 ms |
271528 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
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) { // bigmod
if(p==0) return 1;
int r = bm(b, p/2);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
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;
}
struct segtree_rurq {
// Range update range query, standard form 4 (assignment/sum)
struct node {
int upd = 0;
int ans = 0;
bool exist = 0;
};
vector<node> a;
int mod = 0;
//To be remained unchanged
void u(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
a[idx].upd = val;
a[idx].ans = val * (constr-constl+1);
a[idx].exist = 1;
if(mod) {
a[idx].upd %= mod;
a[idx].ans %= mod;
}
return;
}
int mid = (constl+constr) >> 1;
//Lazy propagation
if(a[idx].exist == 1) {
a[2*idx+1].upd = a[idx].upd;
a[2*idx+2].upd = a[idx].upd;
a[idx].upd = 0;
a[2*idx+1].exist = 1;
a[2*idx+2].exist = 1;
a[idx].exist = 0;
a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
}
if(mid<l || r<constl) u(l, r, mid+1, constr, 2*idx+2, val);
else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
else {
u(l, r, constl, mid, 2*idx+1, val);
u(l, r, mid+1, constr, 2*idx+2, val);
}
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
if(mod) a[idx].ans %= mod;
}
int qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return a[idx].ans;
int mid = (constl+constr) >> 1;
int ret;
if(a[idx].exist == 1) {
a[2*idx+1].upd = a[idx].upd;
a[2*idx+2].upd = a[idx].upd;
a[idx].upd = 0;
a[2*idx+1].exist = 1;
a[2*idx+2].exist = 1;
a[idx].exist = 0;
a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
}
if(mid<l || r<constl) {
ret = qu(l, r, mid+1, constr, 2*idx+2);
}
else if(constr<l || r<mid+1) {
ret = qu(l, r, constl, mid, 2*idx+1);
}
else {
ret = qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
}
if(mod) ret %= mod;
return ret;
}
int sz;
public:
void set_mod(int x) {
mod = x;
}
void update(int l, int r, int v) {
u(l, r, 0, sz, 0, v);
}
int query(int l, int r) {
return qu(l, r, 0, sz, 0);
}
void resize(int k) {
sz = k;
a.resize(4*k + 10);
}
};
int code(char c) {
return (c == 'O' ? 1 : (c == 'I' ? 2 : 0));
}
void solve(int tc) {
int N;
cin >> N;
string s[9];
string word = "JOI";
for(int i=0; i<3; i++) {
cin >> s[i];
for(int j=0; j<N; j++) s[i] += word[rnd(0, 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]);
segtree_rurq st[9][3][3];
int dist[9] = {};
int Q = 200000;
cin >> Q;
string t0;
for(int j=0; j<N; j++) t0 += word[rnd(0, 2)];
cin >> t0;
for(int i=0; i<9; i++) {
for(int j=0; j<N; j++) {
if(t0[j] != s[i][j]) dist[i]++;
}
}
vector<int> lis[9][3];
for(int i=0; i<9; i++) {
for(int j=0; j<N; j++) {
lis[i][code(s[i][j])].push_back(j+1);
}
}
for(int i=0; i<9; i++) {
for(int j=0; j<3; j++) {
for(int k=0; k<3; k++) {
if(lis[i][j].empty()) continue;
st[i][j][k].resize(lis[i][j].size());
for(int l=0; l<lis[i][j].size(); l++) {
if(t0[lis[i][j][l] - 1] == word[k]) {
st[i][j][k].update(l+1, l+1, 1);
}
}
}
}
}
int d = (N <= 100 ? 9 : 1);
for(int i=0; i<=Q; i++) {
if(i > 0) {
int l, r;
l = rnd(1, N), r = rnd(1, N);
if(l > r) swap(l, r);
cin >> l >> r;
char c;
c = word[rnd(0, 2)];
cin >> c;
int L[d][3], R[d][3];
for(int j=0; j<d; j++) {
for(int k=0; k<3; k++) {
if(lis[j][k].empty()) {
L[j][k] = R[j][k] = -1;
continue;
}
int lb = 0, rb = lis[j][k].size() - 1;
while(lb < rb) {
int mid = (lb+rb) >> 1;
if(lis[j][k][mid] >= l) rb = mid;
else lb = mid+1;
}
L[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
lb = 0, rb = lis[j][k].size() - 1;
while(lb < rb) {
int mid = (lb+rb+1) >> 1;
if(lis[j][k][mid] <= r) lb = mid;
else rb = mid-1;
}
R[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
}
}
for(int j=0; j<d; j++) {
for(int k=0; k<3; k++) {
if(L[j][k] == -1 || R[j][k] == -1) continue;
for(int m=0; m<3; m++) {
st[j][k][m].update(L[j][k], R[j][k], 0);
}
st[j][k][code(c)].update(L[j][k], R[j][k], 1);
}
dist[j] = 0;
for(int k=0; k<3; k++) {
if(lis[j][k].empty()) continue;
for(int m=0; m<3; m++) {
if(k != m) dist[j] += st[j][k][m].query(1, lis[j][k].size());
}
}
}
}
bool ret = 0;
for(int j=0; j<d; j++) {
ret |= (dist[j] == 0);
}
cout << (ret ? "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:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<a.size(); i++) {
| ~^~~~~~~~~
Main.cpp: In function 'void solve(int)':
Main.cpp:161:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int l=0; l<lis[i][j].size(); l++) {
| ~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1479 ms |
1204 KB |
Output is correct |
2 |
Correct |
1854 ms |
1204 KB |
Output is correct |
3 |
Correct |
2230 ms |
1180 KB |
Output is correct |
4 |
Correct |
1498 ms |
1176 KB |
Output is correct |
5 |
Correct |
1397 ms |
1144 KB |
Output is correct |
6 |
Correct |
1464 ms |
1112 KB |
Output is correct |
7 |
Correct |
1344 ms |
1272 KB |
Output is correct |
8 |
Correct |
1644 ms |
1292 KB |
Output is correct |
9 |
Correct |
1628 ms |
1280 KB |
Output is correct |
10 |
Correct |
1597 ms |
1208 KB |
Output is correct |
11 |
Correct |
1593 ms |
1384 KB |
Output is correct |
12 |
Correct |
1613 ms |
1308 KB |
Output is correct |
13 |
Correct |
1573 ms |
1344 KB |
Output is correct |
14 |
Correct |
1595 ms |
1196 KB |
Output is correct |
15 |
Correct |
1549 ms |
1448 KB |
Output is correct |
16 |
Correct |
1623 ms |
1140 KB |
Output is correct |
17 |
Correct |
1564 ms |
1232 KB |
Output is correct |
18 |
Correct |
1102 ms |
1376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1479 ms |
1204 KB |
Output is correct |
2 |
Correct |
1854 ms |
1204 KB |
Output is correct |
3 |
Correct |
2230 ms |
1180 KB |
Output is correct |
4 |
Correct |
1498 ms |
1176 KB |
Output is correct |
5 |
Correct |
1397 ms |
1144 KB |
Output is correct |
6 |
Correct |
1464 ms |
1112 KB |
Output is correct |
7 |
Correct |
1344 ms |
1272 KB |
Output is correct |
8 |
Correct |
1644 ms |
1292 KB |
Output is correct |
9 |
Correct |
1628 ms |
1280 KB |
Output is correct |
10 |
Correct |
1597 ms |
1208 KB |
Output is correct |
11 |
Correct |
1593 ms |
1384 KB |
Output is correct |
12 |
Correct |
1613 ms |
1308 KB |
Output is correct |
13 |
Correct |
1573 ms |
1344 KB |
Output is correct |
14 |
Correct |
1595 ms |
1196 KB |
Output is correct |
15 |
Correct |
1549 ms |
1448 KB |
Output is correct |
16 |
Correct |
1623 ms |
1140 KB |
Output is correct |
17 |
Correct |
1564 ms |
1232 KB |
Output is correct |
18 |
Correct |
1102 ms |
1376 KB |
Output is correct |
19 |
Correct |
1928 ms |
269100 KB |
Output is correct |
20 |
Correct |
1904 ms |
266200 KB |
Output is correct |
21 |
Correct |
1157 ms |
250664 KB |
Output is correct |
22 |
Correct |
1143 ms |
225136 KB |
Output is correct |
23 |
Correct |
544 ms |
14960 KB |
Output is correct |
24 |
Correct |
582 ms |
14980 KB |
Output is correct |
25 |
Correct |
1346 ms |
268576 KB |
Output is correct |
26 |
Correct |
1321 ms |
268816 KB |
Output is correct |
27 |
Correct |
1324 ms |
266700 KB |
Output is correct |
28 |
Correct |
1328 ms |
268508 KB |
Output is correct |
29 |
Correct |
1312 ms |
259288 KB |
Output is correct |
30 |
Correct |
591 ms |
15040 KB |
Output is correct |
31 |
Correct |
1296 ms |
266904 KB |
Output is correct |
32 |
Correct |
1241 ms |
242912 KB |
Output is correct |
33 |
Correct |
551 ms |
14648 KB |
Output is correct |
34 |
Correct |
1375 ms |
266632 KB |
Output is correct |
35 |
Correct |
1104 ms |
199016 KB |
Output is correct |
36 |
Correct |
556 ms |
14736 KB |
Output is correct |
37 |
Correct |
558 ms |
14716 KB |
Output is correct |
38 |
Correct |
940 ms |
266660 KB |
Output is correct |
39 |
Correct |
838 ms |
268512 KB |
Output is correct |
40 |
Correct |
870 ms |
174896 KB |
Output is correct |
41 |
Correct |
1112 ms |
266692 KB |
Output is correct |
42 |
Correct |
694 ms |
266648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1479 ms |
1204 KB |
Output is correct |
2 |
Correct |
1854 ms |
1204 KB |
Output is correct |
3 |
Correct |
2230 ms |
1180 KB |
Output is correct |
4 |
Correct |
1498 ms |
1176 KB |
Output is correct |
5 |
Correct |
1397 ms |
1144 KB |
Output is correct |
6 |
Correct |
1464 ms |
1112 KB |
Output is correct |
7 |
Correct |
1344 ms |
1272 KB |
Output is correct |
8 |
Correct |
1644 ms |
1292 KB |
Output is correct |
9 |
Correct |
1628 ms |
1280 KB |
Output is correct |
10 |
Correct |
1597 ms |
1208 KB |
Output is correct |
11 |
Correct |
1593 ms |
1384 KB |
Output is correct |
12 |
Correct |
1613 ms |
1308 KB |
Output is correct |
13 |
Correct |
1573 ms |
1344 KB |
Output is correct |
14 |
Correct |
1595 ms |
1196 KB |
Output is correct |
15 |
Correct |
1549 ms |
1448 KB |
Output is correct |
16 |
Correct |
1623 ms |
1140 KB |
Output is correct |
17 |
Correct |
1564 ms |
1232 KB |
Output is correct |
18 |
Correct |
1102 ms |
1376 KB |
Output is correct |
19 |
Correct |
2156 ms |
992 KB |
Output is correct |
20 |
Correct |
2405 ms |
1132 KB |
Output is correct |
21 |
Correct |
1754 ms |
1012 KB |
Output is correct |
22 |
Correct |
1349 ms |
1120 KB |
Output is correct |
23 |
Correct |
1713 ms |
1316 KB |
Output is correct |
24 |
Correct |
1586 ms |
1148 KB |
Output is correct |
25 |
Correct |
1774 ms |
1296 KB |
Output is correct |
26 |
Correct |
1461 ms |
1120 KB |
Output is correct |
27 |
Correct |
1743 ms |
1188 KB |
Output is correct |
28 |
Correct |
1504 ms |
1124 KB |
Output is correct |
29 |
Correct |
1744 ms |
1192 KB |
Output is correct |
30 |
Correct |
1350 ms |
1184 KB |
Output is correct |
31 |
Correct |
1885 ms |
1240 KB |
Output is correct |
32 |
Correct |
1840 ms |
1204 KB |
Output is correct |
33 |
Correct |
1858 ms |
1204 KB |
Output is correct |
34 |
Correct |
1503 ms |
1308 KB |
Output is correct |
35 |
Correct |
1885 ms |
1296 KB |
Output is correct |
36 |
Correct |
1866 ms |
1508 KB |
Output is correct |
37 |
Correct |
1885 ms |
1380 KB |
Output is correct |
38 |
Correct |
1847 ms |
1308 KB |
Output is correct |
39 |
Correct |
1891 ms |
1184 KB |
Output is correct |
40 |
Correct |
1878 ms |
1360 KB |
Output is correct |
41 |
Correct |
1841 ms |
1276 KB |
Output is correct |
42 |
Correct |
1853 ms |
1280 KB |
Output is correct |
43 |
Correct |
1621 ms |
1248 KB |
Output is correct |
44 |
Correct |
1892 ms |
1184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1479 ms |
1204 KB |
Output is correct |
2 |
Correct |
1854 ms |
1204 KB |
Output is correct |
3 |
Correct |
2230 ms |
1180 KB |
Output is correct |
4 |
Correct |
1498 ms |
1176 KB |
Output is correct |
5 |
Correct |
1397 ms |
1144 KB |
Output is correct |
6 |
Correct |
1464 ms |
1112 KB |
Output is correct |
7 |
Correct |
1344 ms |
1272 KB |
Output is correct |
8 |
Correct |
1644 ms |
1292 KB |
Output is correct |
9 |
Correct |
1628 ms |
1280 KB |
Output is correct |
10 |
Correct |
1597 ms |
1208 KB |
Output is correct |
11 |
Correct |
1593 ms |
1384 KB |
Output is correct |
12 |
Correct |
1613 ms |
1308 KB |
Output is correct |
13 |
Correct |
1573 ms |
1344 KB |
Output is correct |
14 |
Correct |
1595 ms |
1196 KB |
Output is correct |
15 |
Correct |
1549 ms |
1448 KB |
Output is correct |
16 |
Correct |
1623 ms |
1140 KB |
Output is correct |
17 |
Correct |
1564 ms |
1232 KB |
Output is correct |
18 |
Correct |
1102 ms |
1376 KB |
Output is correct |
19 |
Correct |
1928 ms |
269100 KB |
Output is correct |
20 |
Correct |
1904 ms |
266200 KB |
Output is correct |
21 |
Correct |
1157 ms |
250664 KB |
Output is correct |
22 |
Correct |
1143 ms |
225136 KB |
Output is correct |
23 |
Correct |
544 ms |
14960 KB |
Output is correct |
24 |
Correct |
582 ms |
14980 KB |
Output is correct |
25 |
Correct |
1346 ms |
268576 KB |
Output is correct |
26 |
Correct |
1321 ms |
268816 KB |
Output is correct |
27 |
Correct |
1324 ms |
266700 KB |
Output is correct |
28 |
Correct |
1328 ms |
268508 KB |
Output is correct |
29 |
Correct |
1312 ms |
259288 KB |
Output is correct |
30 |
Correct |
591 ms |
15040 KB |
Output is correct |
31 |
Correct |
1296 ms |
266904 KB |
Output is correct |
32 |
Correct |
1241 ms |
242912 KB |
Output is correct |
33 |
Correct |
551 ms |
14648 KB |
Output is correct |
34 |
Correct |
1375 ms |
266632 KB |
Output is correct |
35 |
Correct |
1104 ms |
199016 KB |
Output is correct |
36 |
Correct |
556 ms |
14736 KB |
Output is correct |
37 |
Correct |
558 ms |
14716 KB |
Output is correct |
38 |
Correct |
940 ms |
266660 KB |
Output is correct |
39 |
Correct |
838 ms |
268512 KB |
Output is correct |
40 |
Correct |
870 ms |
174896 KB |
Output is correct |
41 |
Correct |
1112 ms |
266692 KB |
Output is correct |
42 |
Correct |
694 ms |
266648 KB |
Output is correct |
43 |
Correct |
2156 ms |
992 KB |
Output is correct |
44 |
Correct |
2405 ms |
1132 KB |
Output is correct |
45 |
Correct |
1754 ms |
1012 KB |
Output is correct |
46 |
Correct |
1349 ms |
1120 KB |
Output is correct |
47 |
Correct |
1713 ms |
1316 KB |
Output is correct |
48 |
Correct |
1586 ms |
1148 KB |
Output is correct |
49 |
Correct |
1774 ms |
1296 KB |
Output is correct |
50 |
Correct |
1461 ms |
1120 KB |
Output is correct |
51 |
Correct |
1743 ms |
1188 KB |
Output is correct |
52 |
Correct |
1504 ms |
1124 KB |
Output is correct |
53 |
Correct |
1744 ms |
1192 KB |
Output is correct |
54 |
Correct |
1350 ms |
1184 KB |
Output is correct |
55 |
Correct |
1885 ms |
1240 KB |
Output is correct |
56 |
Correct |
1840 ms |
1204 KB |
Output is correct |
57 |
Correct |
1858 ms |
1204 KB |
Output is correct |
58 |
Correct |
1503 ms |
1308 KB |
Output is correct |
59 |
Correct |
1885 ms |
1296 KB |
Output is correct |
60 |
Correct |
1866 ms |
1508 KB |
Output is correct |
61 |
Correct |
1885 ms |
1380 KB |
Output is correct |
62 |
Correct |
1847 ms |
1308 KB |
Output is correct |
63 |
Correct |
1891 ms |
1184 KB |
Output is correct |
64 |
Correct |
1878 ms |
1360 KB |
Output is correct |
65 |
Correct |
1841 ms |
1276 KB |
Output is correct |
66 |
Correct |
1853 ms |
1280 KB |
Output is correct |
67 |
Correct |
1621 ms |
1248 KB |
Output is correct |
68 |
Correct |
1892 ms |
1184 KB |
Output is correct |
69 |
Correct |
1660 ms |
226808 KB |
Output is correct |
70 |
Incorrect |
1759 ms |
271528 KB |
Output isn't correct |
71 |
Halted |
0 ms |
0 KB |
- |