QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643264 | #2097. Letters | test123 | 100 ✓ | 39ms | 17588kb | C++14 | 830b | 2024-10-15 20:12:56 | 2024-10-15 20:12:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int read(){
int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}
return ret*f;
}
int n;
long long ans;
int a[maxn],nxt[maxn],lnk[26];
char ch1[maxn],ch2[maxn];
int tree[maxn];
void add(int x){
for(;x<=n;x+=x&-x) tree[x]++;
}
int get(int x){
int ret=0;
for(;x;x-=x&-x) ret+=tree[x];
return ret;
}
int main(){
n=read();
scanf("%s",ch1+1);
scanf("%s",ch2+1);
for(int i=1;i<=n;++i){
int p=ch1[i]-'A';
nxt[i]=lnk[p];
lnk[p]=i;
}
for(int i=n;i;--i){
int p=ch2[i]-'A';
a[i]=lnk[p];
lnk[p]=nxt[lnk[p]];
}
for(int i=1;i<=n;++i){
ans+=i-1-get(a[i]);
add(a[i]);
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 7960kb
input:
4 AACB BACA
output:
4
result:
ok single line: '4'
Test #2:
score: 10
Accepted
time: 1ms
memory: 7984kb
input:
2 AB BA
output:
1
result:
ok single line: '1'
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 1ms
memory: 10100kb
input:
7 AABCDDD DDDBCAA
output:
16
result:
ok single line: '16'
Test #4:
score: 10
Accepted
time: 1ms
memory: 10044kb
input:
10 BAAAAAAAAA AAAAAAAAAB
output:
9
result:
ok single line: '9'
Subtask #3:
score: 10
Accepted
Test #5:
score: 10
Accepted
time: 1ms
memory: 9900kb
input:
1000 POJOBCHASLIAZBGBJWRTRYTDDRZKJIVZAPJYUQFJGYBDZXCGZMGJOVAHKKZYDJMBFUPJMETVLEQRVBUHBGAJPKPOFJUJKROMSJPARTFRLBZRODFGWPIVPAIWCRZBUGVRGQVDUWLPHUYUJOIKZNYWGYHNNTVHGZMRZXNRAPSKKXTOYVYEVZVREPUQQOLMQIRWFWSDZHDJFWSVBRLPAUHTFCHRWATUXKJFDLDZBCVXSAPEYHZZWTIIBIKJOWYHBJIIGUHNVTRTNFIJRXOUZYFLUJNBGXWVZQOCGWWJDQA...
output:
44599
result:
ok single line: '44599'
Test #6:
score: 10
Accepted
time: 1ms
memory: 9968kb
input:
1000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGHHHHHHHHHHHHHHHHHHHHHHHHH...
output:
480766
result:
ok single line: '480766'
Test #7:
score: 10
Accepted
time: 0ms
memory: 10048kb
input:
3 ABB BAB
output:
1
result:
ok single line: '1'
Subtask #4:
score: 10
Accepted
Test #8:
score: 10
Accepted
time: 0ms
memory: 9956kb
input:
10000 RMVEBKEFDDSQAXBIILNDFROEZAZVNGTFWTJDMRWVOGMDUSYLWFAPEZYXOYVCKCIDCPGQPOBEPWSTSNEWJXDFVPXVXZKBUADALDZUYKXKJHDWPATMMFACHAOXBHFNSTVBGPSBERMVDQEXAMVOOIQGVHKZXNKVPUMBNBYYNHGIXNGVODHWLTLNBFBCYNRXZOBQERHFMDEUCOGQVEBXSJLLVDZPRZPZNAANUKHAYMSQLXBYWUKVNGPTZFWWMFRSQVVNSSAPJDXPJTQPGPXWONIDLNVRBBDHHVUZGWCMWL...
output:
1499627
result:
ok single line: '1499627'
Test #9:
score: 10
Accepted
time: 1ms
memory: 10096kb
input:
10000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
48076920
result:
ok single line: '48076920'
Test #10:
score: 10
Accepted
time: 1ms
memory: 8016kb
input:
7 ZZZAAAA ZAAZAAZ
output:
6
result:
ok single line: '6'
Subtask #5:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 3ms
memory: 10460kb
input:
50000 WIAFULWCNVMCWHRCOTVNUGYNIDULFEQYHUBOXPLQBDAPQVQWOQKHQIVXCBYGVUJJIJIOAVESOQTKQLXYZVKSAROQHXMJJNWLLBDGATXOVADSBUJLQEQTTWSYBHVAGAXTZUDVDBKZTUSWTTUECPTIHJZEHWWTSQTWNEEVVGQJFFPMUQRUCGUGXUSUVPVAHNHTDQCLOXTSELYDAINUQUZWNDCTLDHCRTCREEJXRZHLJQZJIUJMYIKZXGSCBDSFRIUHBXRJSOLMOAAZOOORPHKFFVGVOIWBCLYNKZFNVB...
output:
17536625
result:
ok single line: '17536625'
Test #12:
score: 10
Accepted
time: 0ms
memory: 10108kb
input:
50000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
1201923076
result:
ok single line: '1201923076'
Test #13:
score: 10
Accepted
time: 24ms
memory: 17052kb
input:
900000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
899000000
result:
ok single line: '899000000'
Subtask #6:
score: 10
Accepted
Test #14:
score: 10
Accepted
time: 5ms
memory: 12392kb
input:
100000 VEVEIWYVIDHDRWMWYMNHQTZAVZDXJNGFMHKLXFXNFPITDGHRFDVQJIZSXVMNQABLVGTGRHVHGXAVDJGAAHBYOKNGHUUTQHPCQHPYFEPHEWCAFAYDPTDMDSAMJNITISNBNGJZTSSPWJRHCBPFRPJZWKOWFTCMBSLVBUZFYIPXSKOBXNFIYFMYVYSUASDDICODOJBATNFJGGNPXIHSZEOFVDIAMKJRPKUVGHJMCWXWXTSMTNAXVGYRLMAKPSYYXIRJAOWKTEAAELYMUTCSUXOOPDLQHUURAEVDBVMJH...
output:
47167845
result:
ok single line: '47167845'
Test #15:
score: 10
Accepted
time: 0ms
memory: 8708kb
input:
100000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
4807692306
result:
ok single line: '4807692306'
Subtask #7:
score: 10
Accepted
Test #16:
score: 10
Accepted
time: 4ms
memory: 16240kb
input:
200000 NUCKAWZSGUDPEOWOVSPGYYLGGRNIMRFKGBBXYITCKKDYLPQMADTEIPEJUAIMFQNONUVNJWZIJDVIKVXHKKWRFCDIHZINAMRILJMEDWJZQSHXHBRTMSHYBORAHSDUSNDRFXOXRJXCZNSHYTQBHXNILRJKVKNTMZBGEBPKOJWLEQRWKNPVJVSZNMNQUFXAMWNKHGYAMDDKTZUJSQDNEFHHJZVVNUWINJBZXONPLMDUHGIEADRVQJZFOGRLAPOOCIXSJBCYWMRUHXIHQAOSUKBMBUIQQBMOJKDUJFCFW...
output:
130542635
result:
ok single line: '130542635'
Test #17:
score: 10
Accepted
time: 3ms
memory: 12788kb
input:
200000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
19230769228
result:
ok single line: '19230769228'
Subtask #8:
score: 10
Accepted
Test #18:
score: 10
Accepted
time: 16ms
memory: 16260kb
input:
500000 YUSRCBAHKTWBDZFNBNKCWCWUGHILEMCSONDCPCRWAOYBTQACCSIQTDOZODXQLJYCLAXSDFTUOAOSBGRVWSSRNNVZBPECSTHFATSHXWCALBPFDDZJKTBVDZHTOOMOJCGIKOZVNONAVOYMMGZVKVZINFMRVCUNHMVEFXIDNJZIIATLUECIRPGHLOVDSHUUKWSTHHYVHIGXNRHBSMNJXIAEYWUDTLHSQKNXTGEXISCQJLITUJGRNHMBWTBVNWAOQLRSJDBNRLRWDOFTWHFTFXLUBRYYMIOFEKEYPJOXN...
output:
580934901
result:
ok single line: '580934901'
Test #19:
score: 10
Accepted
time: 7ms
memory: 16020kb
input:
500000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
120192307690
result:
ok single line: '120192307690'
Subtask #9:
score: 10
Accepted
Test #20:
score: 10
Accepted
time: 34ms
memory: 17504kb
input:
1000000 ZMNYCQJXRAIOTVJWLLTJSMFAEQKSXUGQEZHDELAYLFUPWXXFCECMPUMOTSPORSOAJHFOSIGVZUMYEBYHRSYNNHSQPJCVACTXQBWZKERTQRDCSZQVTSGIHQAIQFUOXLXBTVIZJIFMHXZBHJKZNJXJURXNBPTDDLCQPNPDSRWTKGSCCLDXYFLXWASWAZNJJLBHELLVYXMLOKFLHOJEJNSYRORUYJHCXREIMKDXSJDLVLPGKQLJUMPDPRVHUYMIWBZVMFOKGJPOTLNTFYYHXNCHENLPBHSUPMCVFSBA...
output:
1482550867
result:
ok single line: '1482550867'
Test #21:
score: 10
Accepted
time: 28ms
memory: 17488kb
input:
1000000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
480769230766
result:
ok single line: '480769230766'
Subtask #10:
score: 10
Accepted
Test #22:
score: 10
Accepted
time: 39ms
memory: 17588kb
input:
1000000 DKJNLAZQBNGZSAIREFHTEWQWBWKVMBQNPSQKBYZOSCXMSYIJGRKEOKQDFLCRCBHSKJNCBSWGQQRGRNFTBSMWEGULVSZZIMWRYFWETYYMNFPGIOIDUNJVPJAYTVALPVJEBUDYKTKYAQDPEKTMPCSKXXCTBTTYQYEWIDDCTCOJKXEFSPMLYYWQJZPOZXNMIRHJZLLEFJFJDNEXXSKDQRSYPWEOTZYBALVEVSQAAGSOVEBIPHMOTSVETPMYOQXFIYAEDNYQIWLBMGEQHDKABQSKHBRPPYUEVBZJDLII...
output:
1819136406
result:
ok single line: '1819136406'
Test #23:
score: 10
Accepted
time: 24ms
memory: 17444kb
input:
1000000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
480769230766
result:
ok single line: '480769230766'
Extra Test:
score: 0
Extra Test Passed