#include "dna.h"'
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int tree[N][3][3], n;
void upd(int id, int t1, int t2) {
++id;
for(id; id <= n; id += id & (-id)) tree[id][t1][t2] ++;
}
int get(int id, int t1, int t2) {
++id;
int ans = 0;
for(id; id >= 1; id -= id & (-id)) ans += tree[id][t1][t2];
return ans;
}
void init(std::string a, std::string b) {
n = a.size();
for(int i = 0; i < n; i++) {
upd(i, (a[i] == 'A' ? 1 : a[i] == 'C' ? 0 : 2), (b[i] == 'A' ? 1 : b[i] == 'C' ? 0 : 2));
}
}
int get_distance(int x, int y) {
vector<vector<int> > a;
a.resize(3, vector<int> (3));
int ans = 0;
vector<int> X(3);
for(int t1 = 0; t1 < 3; t1++) {
for(int t2 = 0; t2 < 3; t2++) {
a[t1][t2] = get(y, t1, t2) - get(x - 1, t1, t2);
X[t2] += a[t1][t2];
X[t1] -= a[t1][t2];
}
}
for(int t1 = 0; t1 < 3; t1++) {
if(X[t1]) return -1;
}
for(int t1 = 0; t1 < 3; t1++) {
for(int t2 = t1 + 1; t2 < 3; t2++) {
int xx = min(a[t1][t2], a[t2][t1]);
a[t1][t2] -= xx;
a[t2][t1] -= xx;
ans += xx;
}
}
int cn = 0;
for(int t1 = 0; t1 < 3; t1++) {
for(int t2 = 0; t2 < 3; t2++) {
if(t1 == t2) continue;
cn += a[t1][t2];
}
}
return cn / 3 * 2 + ans;
}
/*
int main() {
int n, q;
assert(scanf("%d %d", &n, &q) == 2);
char A[n+1], B[n+1];
assert(scanf("%s", A) == 1);
assert(scanf("%s", B) == 1);
std::string a = std::string(A);
std::string b = std::string(B);
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d %d", &x[i], &y[i]) == 2);
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", results[i]);
}
fclose(stdout);
return 0;
}*/
Compilation message
dna.cpp:1:17: warning: missing terminating ' character
1 | #include "dna.h"'
| ^
dna.cpp:1:17: warning: extra tokens at end of #include directive
dna.cpp: In function 'void upd(int, int, int)':
dna.cpp:8:6: warning: statement has no effect [-Wunused-value]
8 | for(id; id <= n; id += id & (-id)) tree[id][t1][t2] ++;
| ^~
dna.cpp: In function 'int get(int, int, int)':
dna.cpp:13:6: warning: statement has no effect [-Wunused-value]
13 | for(id; id >= 1; id -= id & (-id)) ans += tree[id][t1][t2];
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
6896 KB |
Output is correct |
2 |
Correct |
70 ms |
7036 KB |
Output is correct |
3 |
Correct |
66 ms |
6628 KB |
Output is correct |
4 |
Correct |
68 ms |
6992 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
4564 KB |
Output is correct |
5 |
Correct |
7 ms |
4576 KB |
Output is correct |
6 |
Correct |
6 ms |
4536 KB |
Output is correct |
7 |
Correct |
5 ms |
4220 KB |
Output is correct |
8 |
Correct |
7 ms |
4564 KB |
Output is correct |
9 |
Correct |
6 ms |
4576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
4564 KB |
Output is correct |
5 |
Correct |
7 ms |
4576 KB |
Output is correct |
6 |
Correct |
6 ms |
4536 KB |
Output is correct |
7 |
Correct |
5 ms |
4220 KB |
Output is correct |
8 |
Correct |
7 ms |
4564 KB |
Output is correct |
9 |
Correct |
6 ms |
4576 KB |
Output is correct |
10 |
Correct |
70 ms |
6884 KB |
Output is correct |
11 |
Correct |
67 ms |
7048 KB |
Output is correct |
12 |
Correct |
71 ms |
7072 KB |
Output is correct |
13 |
Correct |
69 ms |
7188 KB |
Output is correct |
14 |
Correct |
68 ms |
7372 KB |
Output is correct |
15 |
Correct |
73 ms |
7280 KB |
Output is correct |
16 |
Correct |
83 ms |
6980 KB |
Output is correct |
17 |
Correct |
64 ms |
7104 KB |
Output is correct |
18 |
Correct |
65 ms |
7232 KB |
Output is correct |
19 |
Correct |
62 ms |
7008 KB |
Output is correct |
20 |
Correct |
67 ms |
7060 KB |
Output is correct |
21 |
Correct |
70 ms |
7272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
4564 KB |
Output is correct |
5 |
Correct |
7 ms |
4576 KB |
Output is correct |
6 |
Correct |
6 ms |
4536 KB |
Output is correct |
7 |
Correct |
5 ms |
4220 KB |
Output is correct |
8 |
Correct |
7 ms |
4564 KB |
Output is correct |
9 |
Correct |
6 ms |
4576 KB |
Output is correct |
10 |
Correct |
5 ms |
4180 KB |
Output is correct |
11 |
Correct |
7 ms |
4564 KB |
Output is correct |
12 |
Correct |
6 ms |
4308 KB |
Output is correct |
13 |
Correct |
6 ms |
4564 KB |
Output is correct |
14 |
Correct |
6 ms |
4564 KB |
Output is correct |
15 |
Correct |
5 ms |
4580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
6896 KB |
Output is correct |
2 |
Correct |
70 ms |
7036 KB |
Output is correct |
3 |
Correct |
66 ms |
6628 KB |
Output is correct |
4 |
Correct |
68 ms |
6992 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
6 ms |
4564 KB |
Output is correct |
12 |
Correct |
7 ms |
4576 KB |
Output is correct |
13 |
Correct |
6 ms |
4536 KB |
Output is correct |
14 |
Correct |
5 ms |
4220 KB |
Output is correct |
15 |
Correct |
7 ms |
4564 KB |
Output is correct |
16 |
Correct |
6 ms |
4576 KB |
Output is correct |
17 |
Correct |
70 ms |
6884 KB |
Output is correct |
18 |
Correct |
67 ms |
7048 KB |
Output is correct |
19 |
Correct |
71 ms |
7072 KB |
Output is correct |
20 |
Correct |
69 ms |
7188 KB |
Output is correct |
21 |
Correct |
68 ms |
7372 KB |
Output is correct |
22 |
Correct |
73 ms |
7280 KB |
Output is correct |
23 |
Correct |
83 ms |
6980 KB |
Output is correct |
24 |
Correct |
64 ms |
7104 KB |
Output is correct |
25 |
Correct |
65 ms |
7232 KB |
Output is correct |
26 |
Correct |
62 ms |
7008 KB |
Output is correct |
27 |
Correct |
67 ms |
7060 KB |
Output is correct |
28 |
Correct |
70 ms |
7272 KB |
Output is correct |
29 |
Correct |
5 ms |
4180 KB |
Output is correct |
30 |
Correct |
7 ms |
4564 KB |
Output is correct |
31 |
Correct |
6 ms |
4308 KB |
Output is correct |
32 |
Correct |
6 ms |
4564 KB |
Output is correct |
33 |
Correct |
6 ms |
4564 KB |
Output is correct |
34 |
Correct |
5 ms |
4580 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
66 ms |
6628 KB |
Output is correct |
37 |
Correct |
69 ms |
7048 KB |
Output is correct |
38 |
Correct |
69 ms |
7132 KB |
Output is correct |
39 |
Correct |
72 ms |
7380 KB |
Output is correct |
40 |
Correct |
67 ms |
7372 KB |
Output is correct |
41 |
Correct |
5 ms |
4564 KB |
Output is correct |
42 |
Correct |
71 ms |
7036 KB |
Output is correct |
43 |
Correct |
65 ms |
7272 KB |
Output is correct |
44 |
Correct |
65 ms |
7284 KB |
Output is correct |
45 |
Correct |
63 ms |
7016 KB |
Output is correct |
46 |
Correct |
63 ms |
7292 KB |
Output is correct |
47 |
Correct |
81 ms |
7284 KB |
Output is correct |