QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#643264#2097. Letterstest123100 ✓39ms17588kbC++14830b2024-10-15 20:12:562024-10-15 20:12:57

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 20:12:57]
  • 评测
  • 测评结果:100
  • 用时:39ms
  • 内存:17588kb
  • [2024-10-15 20:12:56]
  • 提交

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