#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
struct Info {
int AonT, AonC;
int TonA, TonC;
int ConA, ConT;
// A, T, C;
};
int n;
Info t[401010];
string A, B;
void build(int v, int vl, int vr) {
if (vl == vr) {
if (A[vl] == B[vl])return;
if (A[vl] == 'A' && B[vl] == 'T')t[v].AonT = 1;
if (A[vl] == 'A' && B[vl] == 'C')t[v].AonC = 1;
if (A[vl] == 'T' && B[vl] == 'A')t[v].TonA = 1;
if (A[vl] == 'T' && B[vl] == 'C')t[v].TonC = 1;
if (A[vl] == 'C' && B[vl] == 'A')t[v].ConA = 1;
if (A[vl] == 'C' && B[vl] == 'T')t[v].ConT = 1;
return;
}
int vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm + 1, vr);
t[v].AonT = t[2 * v].AonT + t[2 * v + 1].AonT;
t[v].AonC = t[2 * v].AonC + t[2 * v + 1].AonC;
t[v].TonA = t[2 * v].TonA + t[2 * v + 1].TonA;
t[v].TonC = t[2 * v].TonC + t[2 * v + 1].TonC;
t[v].ConA = t[2 * v].ConA + t[2 * v + 1].ConA;
t[v].ConT = t[2 * v].ConT + t[2 * v + 1].ConT;
return;
}
Info gt(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)return t[v];
if (r < vl || vr < l)return {0, 0, 0, 0, 0, 0};
int vm = (vl + vr) / 2;
auto f = gt(2 * v, vl, vm, l, r);
auto s = gt(2 * v + 1, vm + 1, vr, l, r);
return {f.AonT + s.AonT, f.AonC + s.AonC,
f.TonA + s.TonA, f.TonC + s.TonC,
f.ConA + s.ConA, f.ConT + s.ConT};
}
int acntA[101010], acntT[101010], acntC[101010];
int bcntA[101010], bcntT[101010], bcntC[101010];
void init(std::string a, std::string b) {
n = a.size();
A = a; B = b;
build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
if (i > 0) {
acntA[i] = acntA[i - 1];
acntT[i] = acntT[i - 1];
acntC[i] = acntC[i - 1];
bcntA[i] = bcntA[i - 1];
bcntT[i] = bcntT[i - 1];
bcntC[i] = bcntC[i - 1];
}
if (a[i] == 'A')acntA[i]++;
if (a[i] == 'T')acntT[i]++;
if (a[i] == 'C')acntC[i]++;
if (b[i] == 'A')bcntA[i]++;
if (b[i] == 'T')bcntT[i]++;
if (b[i] == 'C')bcntC[i]++;
}
}
int get_distance(int x, int y) {
int aA = acntA[y], aT = acntT[y], aC = acntC[y];
if (x > 0){aA -= acntA[x - 1]; aT -= acntT[x - 1]; aC -= acntC[x - 1];}
int bA = bcntA[y], bT = bcntT[y], bC = bcntC[y];
if (x > 0){bA -= bcntA[x - 1]; bT -= bcntT[x - 1]; bC -= bcntC[x - 1];}
if (aA != bA || aT != bT || aC != bC)return -1;
auto have = gt(1, 0, n - 1, x, y);
int ans = 0;
{
int M = min(have.AonT, have.TonA);
have.AonT -= M;
have.TonA -= M;
ans += M;
}
{
int M = min(have.AonC, have.ConA);
have.AonC -= M;
have.ConA -= M;
ans += M;
}
{
int M = min(have.TonC, have.ConT);
have.TonC -= M;
have.ConT -= M;
ans += M;
}
int F = max(have.AonT, have.TonA);
int S = max(have.AonC, have.ConA);
int T = max(have.TonC, have.ConT);
ans += (max({F, S, T}) + max({min(F, S), min(S, T), min(F, T)}));
/*
struct Info {
int AonT, AonC;
int TonA, TonC;
int ConA, ConT;
// A, T, C;
};
*/
return ans;
}
/**
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
10944 KB |
Output is correct |
2 |
Correct |
100 ms |
10960 KB |
Output is correct |
3 |
Correct |
94 ms |
10668 KB |
Output is correct |
4 |
Correct |
96 ms |
10948 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
11 ms |
9564 KB |
Output is correct |
5 |
Correct |
12 ms |
9580 KB |
Output is correct |
6 |
Correct |
10 ms |
9548 KB |
Output is correct |
7 |
Correct |
13 ms |
9376 KB |
Output is correct |
8 |
Correct |
11 ms |
9620 KB |
Output is correct |
9 |
Correct |
9 ms |
9548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
11 ms |
9564 KB |
Output is correct |
5 |
Correct |
12 ms |
9580 KB |
Output is correct |
6 |
Correct |
10 ms |
9548 KB |
Output is correct |
7 |
Correct |
13 ms |
9376 KB |
Output is correct |
8 |
Correct |
11 ms |
9620 KB |
Output is correct |
9 |
Correct |
9 ms |
9548 KB |
Output is correct |
10 |
Correct |
98 ms |
10828 KB |
Output is correct |
11 |
Correct |
100 ms |
10924 KB |
Output is correct |
12 |
Correct |
140 ms |
11096 KB |
Output is correct |
13 |
Correct |
127 ms |
11312 KB |
Output is correct |
14 |
Correct |
129 ms |
11332 KB |
Output is correct |
15 |
Correct |
130 ms |
11244 KB |
Output is correct |
16 |
Correct |
117 ms |
11048 KB |
Output is correct |
17 |
Correct |
113 ms |
11152 KB |
Output is correct |
18 |
Correct |
115 ms |
11332 KB |
Output is correct |
19 |
Correct |
97 ms |
11056 KB |
Output is correct |
20 |
Correct |
99 ms |
11208 KB |
Output is correct |
21 |
Correct |
98 ms |
11344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
11 ms |
9564 KB |
Output is correct |
5 |
Correct |
12 ms |
9580 KB |
Output is correct |
6 |
Correct |
10 ms |
9548 KB |
Output is correct |
7 |
Correct |
13 ms |
9376 KB |
Output is correct |
8 |
Correct |
11 ms |
9620 KB |
Output is correct |
9 |
Correct |
9 ms |
9548 KB |
Output is correct |
10 |
Correct |
10 ms |
9292 KB |
Output is correct |
11 |
Correct |
11 ms |
9592 KB |
Output is correct |
12 |
Correct |
11 ms |
9292 KB |
Output is correct |
13 |
Correct |
12 ms |
9592 KB |
Output is correct |
14 |
Correct |
11 ms |
9500 KB |
Output is correct |
15 |
Correct |
11 ms |
9576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
10944 KB |
Output is correct |
2 |
Correct |
100 ms |
10960 KB |
Output is correct |
3 |
Correct |
94 ms |
10668 KB |
Output is correct |
4 |
Correct |
96 ms |
10948 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
11 ms |
9564 KB |
Output is correct |
12 |
Correct |
12 ms |
9580 KB |
Output is correct |
13 |
Correct |
10 ms |
9548 KB |
Output is correct |
14 |
Correct |
13 ms |
9376 KB |
Output is correct |
15 |
Correct |
11 ms |
9620 KB |
Output is correct |
16 |
Correct |
9 ms |
9548 KB |
Output is correct |
17 |
Correct |
98 ms |
10828 KB |
Output is correct |
18 |
Correct |
100 ms |
10924 KB |
Output is correct |
19 |
Correct |
140 ms |
11096 KB |
Output is correct |
20 |
Correct |
127 ms |
11312 KB |
Output is correct |
21 |
Correct |
129 ms |
11332 KB |
Output is correct |
22 |
Correct |
130 ms |
11244 KB |
Output is correct |
23 |
Correct |
117 ms |
11048 KB |
Output is correct |
24 |
Correct |
113 ms |
11152 KB |
Output is correct |
25 |
Correct |
115 ms |
11332 KB |
Output is correct |
26 |
Correct |
97 ms |
11056 KB |
Output is correct |
27 |
Correct |
99 ms |
11208 KB |
Output is correct |
28 |
Correct |
98 ms |
11344 KB |
Output is correct |
29 |
Correct |
10 ms |
9292 KB |
Output is correct |
30 |
Correct |
11 ms |
9592 KB |
Output is correct |
31 |
Correct |
11 ms |
9292 KB |
Output is correct |
32 |
Correct |
12 ms |
9592 KB |
Output is correct |
33 |
Correct |
11 ms |
9500 KB |
Output is correct |
34 |
Correct |
11 ms |
9576 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
92 ms |
10628 KB |
Output is correct |
37 |
Correct |
102 ms |
10968 KB |
Output is correct |
38 |
Correct |
125 ms |
11112 KB |
Output is correct |
39 |
Correct |
132 ms |
11324 KB |
Output is correct |
40 |
Correct |
135 ms |
11332 KB |
Output is correct |
41 |
Correct |
9 ms |
9620 KB |
Output is correct |
42 |
Correct |
115 ms |
11064 KB |
Output is correct |
43 |
Correct |
120 ms |
11332 KB |
Output is correct |
44 |
Correct |
124 ms |
11296 KB |
Output is correct |
45 |
Correct |
98 ms |
11120 KB |
Output is correct |
46 |
Correct |
113 ms |
11340 KB |
Output is correct |
47 |
Correct |
99 ms |
11344 KB |
Output is correct |