#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define tii tuple<int,int,int>
#define fi first
#define se second
#define bp __builtin_popcount
#define nmax 100010
#define pb emplace_back
int getbit(ll x,int y)
{
return (x>>y)&1;
}
ll getoff(ll x,int y)
{
return x^((1ll)<<y);
}
using namespace std;
struct node
{
int AT,AC,TA,TC,CA,CT;
node() {}
};
int n,q;
string a,b;
node pre[nmax];
void init(string aa,string bb)
{
a=aa; b=bb;
n=a.length();
for (int i=0;i<n;++i)
{
pre[i]=pre[i-1];
if (a[i]=='A')
{
if (b[i]=='C') ++pre[i].AC;
else if (b[i]=='T') ++pre[i].AT;
}
else if (a[i]=='C')
{
if (b[i]=='A') ++pre[i].CA;
else if (b[i]=='T') ++pre[i].CT;
}
else if (a[i]=='T')
{
if (b[i]=='A') ++pre[i].TA;
else if (b[i]=='C') ++pre[i].TC;
}
}
}
int get_distance(int x,int y)
{
int AC=pre[y].AC-pre[x-1].AC;
int AT=pre[y].AT-pre[x-1].AT;
int CA=pre[y].CA-pre[x-1].CA;
int CT=pre[y].CT-pre[x-1].CT;
int TA=pre[y].TA-pre[x-1].TA;
int TC=pre[y].TC-pre[x-1].TC;
if (AC+AT!=CA+TA) return -1;
if (CA+CT!=AC+TC) return -1;
if (TA+TC!=AT+CT) return -1;
int ans1=AC+AT;
if (AC>CA) ans1+=CT;
else if (AT>TA) ans1+=TC;
else ans1+=CT;
int ans2=CA+CT;
if (CA>AC) ans2+=AT;
else if (CT>TC) ans2+=TA;
else ans2+=AT;
int ans3=TA+TC;
if (TA>AT) ans3+=AC;
else if (TC>CT) ans3+=CA;
else ans3+=AC;
int res=min({ans1,ans2,ans3});
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
4676 KB |
Output is correct |
2 |
Correct |
40 ms |
4676 KB |
Output is correct |
3 |
Correct |
39 ms |
4468 KB |
Output is correct |
4 |
Correct |
40 ms |
4800 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
3276 KB |
Output is correct |
5 |
Correct |
5 ms |
3316 KB |
Output is correct |
6 |
Correct |
5 ms |
3404 KB |
Output is correct |
7 |
Correct |
4 ms |
3172 KB |
Output is correct |
8 |
Correct |
4 ms |
3404 KB |
Output is correct |
9 |
Correct |
3 ms |
3404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
3276 KB |
Output is correct |
5 |
Correct |
5 ms |
3316 KB |
Output is correct |
6 |
Correct |
5 ms |
3404 KB |
Output is correct |
7 |
Correct |
4 ms |
3172 KB |
Output is correct |
8 |
Correct |
4 ms |
3404 KB |
Output is correct |
9 |
Correct |
3 ms |
3404 KB |
Output is correct |
10 |
Correct |
39 ms |
4736 KB |
Output is correct |
11 |
Correct |
41 ms |
4676 KB |
Output is correct |
12 |
Correct |
42 ms |
4904 KB |
Output is correct |
13 |
Correct |
40 ms |
4920 KB |
Output is correct |
14 |
Correct |
46 ms |
5056 KB |
Output is correct |
15 |
Correct |
39 ms |
4968 KB |
Output is correct |
16 |
Correct |
37 ms |
4904 KB |
Output is correct |
17 |
Correct |
38 ms |
4932 KB |
Output is correct |
18 |
Correct |
40 ms |
5132 KB |
Output is correct |
19 |
Correct |
37 ms |
4900 KB |
Output is correct |
20 |
Correct |
38 ms |
4936 KB |
Output is correct |
21 |
Correct |
38 ms |
5184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
3276 KB |
Output is correct |
5 |
Correct |
5 ms |
3316 KB |
Output is correct |
6 |
Correct |
5 ms |
3404 KB |
Output is correct |
7 |
Correct |
4 ms |
3172 KB |
Output is correct |
8 |
Correct |
4 ms |
3404 KB |
Output is correct |
9 |
Correct |
3 ms |
3404 KB |
Output is correct |
10 |
Correct |
4 ms |
3148 KB |
Output is correct |
11 |
Correct |
5 ms |
3404 KB |
Output is correct |
12 |
Correct |
5 ms |
3148 KB |
Output is correct |
13 |
Correct |
5 ms |
3404 KB |
Output is correct |
14 |
Correct |
5 ms |
3404 KB |
Output is correct |
15 |
Correct |
4 ms |
3432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
4676 KB |
Output is correct |
2 |
Correct |
40 ms |
4676 KB |
Output is correct |
3 |
Correct |
39 ms |
4468 KB |
Output is correct |
4 |
Correct |
40 ms |
4800 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
5 ms |
3276 KB |
Output is correct |
12 |
Correct |
5 ms |
3316 KB |
Output is correct |
13 |
Correct |
5 ms |
3404 KB |
Output is correct |
14 |
Correct |
4 ms |
3172 KB |
Output is correct |
15 |
Correct |
4 ms |
3404 KB |
Output is correct |
16 |
Correct |
3 ms |
3404 KB |
Output is correct |
17 |
Correct |
39 ms |
4736 KB |
Output is correct |
18 |
Correct |
41 ms |
4676 KB |
Output is correct |
19 |
Correct |
42 ms |
4904 KB |
Output is correct |
20 |
Correct |
40 ms |
4920 KB |
Output is correct |
21 |
Correct |
46 ms |
5056 KB |
Output is correct |
22 |
Correct |
39 ms |
4968 KB |
Output is correct |
23 |
Correct |
37 ms |
4904 KB |
Output is correct |
24 |
Correct |
38 ms |
4932 KB |
Output is correct |
25 |
Correct |
40 ms |
5132 KB |
Output is correct |
26 |
Correct |
37 ms |
4900 KB |
Output is correct |
27 |
Correct |
38 ms |
4936 KB |
Output is correct |
28 |
Correct |
38 ms |
5184 KB |
Output is correct |
29 |
Correct |
4 ms |
3148 KB |
Output is correct |
30 |
Correct |
5 ms |
3404 KB |
Output is correct |
31 |
Correct |
5 ms |
3148 KB |
Output is correct |
32 |
Correct |
5 ms |
3404 KB |
Output is correct |
33 |
Correct |
5 ms |
3404 KB |
Output is correct |
34 |
Correct |
4 ms |
3432 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
40 ms |
4512 KB |
Output is correct |
37 |
Correct |
39 ms |
4812 KB |
Output is correct |
38 |
Correct |
40 ms |
4908 KB |
Output is correct |
39 |
Correct |
43 ms |
5060 KB |
Output is correct |
40 |
Correct |
42 ms |
5060 KB |
Output is correct |
41 |
Correct |
3 ms |
3404 KB |
Output is correct |
42 |
Correct |
38 ms |
4940 KB |
Output is correct |
43 |
Correct |
43 ms |
5064 KB |
Output is correct |
44 |
Correct |
38 ms |
5060 KB |
Output is correct |
45 |
Correct |
36 ms |
4912 KB |
Output is correct |
46 |
Correct |
37 ms |
5108 KB |
Output is correct |
47 |
Correct |
36 ms |
5188 KB |
Output is correct |