#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulHamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename T> vector<int32_t> normalize(vector<T> &rt){vector<int32_t> arr(rt.size());for (int i = 0; i < rt.size(); i++){arr[i]=rt[i];}return arr;}
#define endl '\n'
#define int long long
#define vint(x) vector<int> x
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define tol(bi) (1LL<<((int)(bi)))
#define lsb(x) (x&-x)
const int MOD = 1e9+7;
const int64_t INF = LONG_LONG_MAX;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "dna.h"
struct BIT{
vector<int> fenwik;
BIT(int n){
fenwik.resize(2*n+2,0);
}
void update(int node, int val){
for (node++;node<fenwik.size();node+=lsb(node)) fenwik[node]+=val;
}
int get(int node){
int rval = 0;
for (node++;node;node-=lsb(node)) rval+=fenwik[node];
return rval;
}
int query(int l, int r){
return get(r)-get(l-1);
}
};
vector<BIT> fenwik;
void init(string a, string b) {
int n = a.length();
fenwik.resize(9,BIT(n));
for (int i = 0; i < n; ++i)
{
if (a[i]=='A') a[i]='0';
if (a[i]=='T') a[i]='1';
if (a[i]=='C') a[i]='2';
if (b[i]=='A') b[i]='0';
if (b[i]=='T') b[i]='1';
if (b[i]=='C') b[i]='2';
fenwik[(a[i]-'0')*3+b[i]-'0'].update(i,1);
}
}
int32_t get_distance(int32_t x, int32_t y) {
int at = fenwik[1].query(x,y);
int ac = fenwik[2].query(x,y);
int tc = fenwik[5].query(x,y);
int ta = fenwik[3].query(x,y);
int ca = fenwik[6].query(x,y);
int ct = fenwik[7].query(x,y);
int ans=0;
int temp;
temp = min(at,ta);
ans+=temp;
at-=temp;
ta-=temp;
temp = min(tc,ct);
ans+=temp;
tc-=temp;
ct-=temp;
temp = min(ac,ca);
ans+=temp;
ac-=temp;
ca-=temp;
if (ac+at+tc+ta+ca+ct==0) return ans;
if (!((ac&&ct&&ta) || (at&&tc&&ca))) return -1;
if (ac){
if (ac!=ct || ac!=ta) return -1;
ans+=ac*2;
}
else {
if( ca!=tc || ca!=at) return -1;
ans+=ca*2;
}
return ans;
}
Compilation message
dna.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize("Bismillahirrahmanirrahim")
|
dna.cpp: In member function 'void BIT::update(long long int, long long int)':
dna.cpp:38:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (node++;node<fenwik.size();node+=lsb(node)) fenwik[node]+=val;
| ~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
17468 KB |
Output is correct |
2 |
Correct |
51 ms |
17612 KB |
Output is correct |
3 |
Correct |
51 ms |
16292 KB |
Output is correct |
4 |
Correct |
63 ms |
19004 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
11 ms |
16272 KB |
Output is correct |
5 |
Correct |
10 ms |
16524 KB |
Output is correct |
6 |
Correct |
13 ms |
16376 KB |
Output is correct |
7 |
Correct |
12 ms |
15444 KB |
Output is correct |
8 |
Correct |
12 ms |
16492 KB |
Output is correct |
9 |
Correct |
13 ms |
16468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
11 ms |
16272 KB |
Output is correct |
5 |
Correct |
10 ms |
16524 KB |
Output is correct |
6 |
Correct |
13 ms |
16376 KB |
Output is correct |
7 |
Correct |
12 ms |
15444 KB |
Output is correct |
8 |
Correct |
12 ms |
16492 KB |
Output is correct |
9 |
Correct |
13 ms |
16468 KB |
Output is correct |
10 |
Correct |
52 ms |
17484 KB |
Output is correct |
11 |
Correct |
48 ms |
17628 KB |
Output is correct |
12 |
Correct |
61 ms |
16552 KB |
Output is correct |
13 |
Correct |
68 ms |
17104 KB |
Output is correct |
14 |
Correct |
62 ms |
17604 KB |
Output is correct |
15 |
Correct |
66 ms |
17740 KB |
Output is correct |
16 |
Correct |
54 ms |
16504 KB |
Output is correct |
17 |
Correct |
52 ms |
16968 KB |
Output is correct |
18 |
Correct |
50 ms |
17636 KB |
Output is correct |
19 |
Correct |
48 ms |
16596 KB |
Output is correct |
20 |
Correct |
45 ms |
16960 KB |
Output is correct |
21 |
Correct |
44 ms |
17620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
11 ms |
16272 KB |
Output is correct |
5 |
Correct |
10 ms |
16524 KB |
Output is correct |
6 |
Correct |
13 ms |
16376 KB |
Output is correct |
7 |
Correct |
12 ms |
15444 KB |
Output is correct |
8 |
Correct |
12 ms |
16492 KB |
Output is correct |
9 |
Correct |
13 ms |
16468 KB |
Output is correct |
10 |
Correct |
11 ms |
15060 KB |
Output is correct |
11 |
Correct |
15 ms |
16764 KB |
Output is correct |
12 |
Correct |
12 ms |
15676 KB |
Output is correct |
13 |
Correct |
13 ms |
16596 KB |
Output is correct |
14 |
Correct |
14 ms |
16724 KB |
Output is correct |
15 |
Correct |
14 ms |
16724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
17468 KB |
Output is correct |
2 |
Correct |
51 ms |
17612 KB |
Output is correct |
3 |
Correct |
51 ms |
16292 KB |
Output is correct |
4 |
Correct |
63 ms |
19004 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 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 |
11 ms |
16272 KB |
Output is correct |
12 |
Correct |
10 ms |
16524 KB |
Output is correct |
13 |
Correct |
13 ms |
16376 KB |
Output is correct |
14 |
Correct |
12 ms |
15444 KB |
Output is correct |
15 |
Correct |
12 ms |
16492 KB |
Output is correct |
16 |
Correct |
13 ms |
16468 KB |
Output is correct |
17 |
Correct |
52 ms |
17484 KB |
Output is correct |
18 |
Correct |
48 ms |
17628 KB |
Output is correct |
19 |
Correct |
61 ms |
16552 KB |
Output is correct |
20 |
Correct |
68 ms |
17104 KB |
Output is correct |
21 |
Correct |
62 ms |
17604 KB |
Output is correct |
22 |
Correct |
66 ms |
17740 KB |
Output is correct |
23 |
Correct |
54 ms |
16504 KB |
Output is correct |
24 |
Correct |
52 ms |
16968 KB |
Output is correct |
25 |
Correct |
50 ms |
17636 KB |
Output is correct |
26 |
Correct |
48 ms |
16596 KB |
Output is correct |
27 |
Correct |
45 ms |
16960 KB |
Output is correct |
28 |
Correct |
44 ms |
17620 KB |
Output is correct |
29 |
Correct |
11 ms |
15060 KB |
Output is correct |
30 |
Correct |
15 ms |
16764 KB |
Output is correct |
31 |
Correct |
12 ms |
15676 KB |
Output is correct |
32 |
Correct |
13 ms |
16596 KB |
Output is correct |
33 |
Correct |
14 ms |
16724 KB |
Output is correct |
34 |
Correct |
14 ms |
16724 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
54 ms |
17552 KB |
Output is correct |
37 |
Correct |
52 ms |
19020 KB |
Output is correct |
38 |
Correct |
65 ms |
18020 KB |
Output is correct |
39 |
Correct |
66 ms |
18996 KB |
Output is correct |
40 |
Correct |
60 ms |
18996 KB |
Output is correct |
41 |
Correct |
11 ms |
16732 KB |
Output is correct |
42 |
Correct |
54 ms |
17892 KB |
Output is correct |
43 |
Correct |
55 ms |
18872 KB |
Output is correct |
44 |
Correct |
53 ms |
18892 KB |
Output is correct |
45 |
Correct |
45 ms |
17868 KB |
Output is correct |
46 |
Correct |
48 ms |
18876 KB |
Output is correct |
47 |
Correct |
54 ms |
18860 KB |
Output is correct |