結果
問題 | No.1725 [Cherry 3rd Tune D] 無言の言葉 |
ユーザー | merlin |
提出日時 | 2021-10-29 22:27:17 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 638 ms / 4,000 ms |
コード長 | 2,354 bytes |
コンパイル時間 | 2,698 ms |
コンパイル使用メモリ | 79,616 KB |
実行使用メモリ | 105,568 KB |
最終ジャッジ日時 | 2024-04-16 15:18:22 |
合計ジャッジ時間 | 17,835 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
37,968 KB |
testcase_01 | AC | 74 ms
37,840 KB |
testcase_02 | AC | 100 ms
38,460 KB |
testcase_03 | AC | 116 ms
39,472 KB |
testcase_04 | AC | 90 ms
38,728 KB |
testcase_05 | AC | 102 ms
38,480 KB |
testcase_06 | AC | 170 ms
42,324 KB |
testcase_07 | AC | 144 ms
39,704 KB |
testcase_08 | AC | 167 ms
42,168 KB |
testcase_09 | AC | 92 ms
37,848 KB |
testcase_10 | AC | 133 ms
39,508 KB |
testcase_11 | AC | 83 ms
38,204 KB |
testcase_12 | AC | 191 ms
47,008 KB |
testcase_13 | AC | 190 ms
47,056 KB |
testcase_14 | AC | 327 ms
48,400 KB |
testcase_15 | AC | 198 ms
47,272 KB |
testcase_16 | AC | 211 ms
48,064 KB |
testcase_17 | AC | 236 ms
48,740 KB |
testcase_18 | AC | 352 ms
49,128 KB |
testcase_19 | AC | 228 ms
46,128 KB |
testcase_20 | AC | 186 ms
43,028 KB |
testcase_21 | AC | 326 ms
48,048 KB |
testcase_22 | AC | 412 ms
66,748 KB |
testcase_23 | AC | 406 ms
65,180 KB |
testcase_24 | AC | 331 ms
57,640 KB |
testcase_25 | AC | 478 ms
83,904 KB |
testcase_26 | AC | 445 ms
70,284 KB |
testcase_27 | AC | 437 ms
82,112 KB |
testcase_28 | AC | 557 ms
87,500 KB |
testcase_29 | AC | 506 ms
84,856 KB |
testcase_30 | AC | 512 ms
90,412 KB |
testcase_31 | AC | 363 ms
63,644 KB |
testcase_32 | AC | 638 ms
104,888 KB |
testcase_33 | AC | 597 ms
105,568 KB |
testcase_34 | AC | 584 ms
102,232 KB |
testcase_35 | AC | 579 ms
95,344 KB |
testcase_36 | AC | 574 ms
101,688 KB |
testcase_37 | AC | 312 ms
46,204 KB |
testcase_38 | AC | 318 ms
46,132 KB |
testcase_39 | AC | 317 ms
46,012 KB |
testcase_40 | AC | 319 ms
46,208 KB |
testcase_41 | AC | 318 ms
46,144 KB |
testcase_42 | AC | 75 ms
38,164 KB |
testcase_43 | AC | 306 ms
99,156 KB |
ソースコード
import java.io.*; import java.util.*; class Main { public static void main(String args[])throws Exception { BufferedReader bu=new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb=new StringBuilder(); char a[]=bu.readLine().toCharArray(),b[]=bu.readLine().toCharArray(); int n=a.length,m=b.length; int ca[][][]=new int[2][n+1][26],cb[][][]=new int[2][m+1][26]; cumulative(a,ca); cumulative(b,cb); int q=Integer.parseInt(bu.readLine()); while(q-->0) { String s[]=bu.readLine().split(" "); int l=Integer.parseInt(s[0])-1,r=Integer.parseInt(s[1]),t=s[2].charAt(0)-'a'; long ans=count(ca,cb,r,t)-count(ca,cb,l,t); sb.append(ans+"\n"); } System.out.print(sb); } static void cumulative(char s[],int c[][][]) { int n=s.length,i; for(i=1;i<=n;i++) { //i characters from left int x=s[i-1]-'a',j; for(j=0;j<26;j++) c[0][i][j]=c[0][i-1][j]; c[0][i][x]++; //from right x=s[n-i]-'a'; for(j=0;j<26;j++) c[1][i][j]=c[1][i-1][j]; c[1][i][x]++; } } static long count(int a[][][],int b[][][],int x,int t) { if(x==0) return 0; int n=a[0].length-1,m=b[0].length-1; int times=x/(n+m); long ans=1l*times*a[0][n][t]+1l*times*b[0][m][t]; x-=times*(n+m); if(x<=n) { //L R L R format if(times%2==0) ans+=a[0][x][t]; else ans+=a[1][x][t]; } else { ans+=a[0][n][t]; x-=n; //how to find orientation of iteration in current move? int or=orientation(times+1); if(or==0) ans+=b[0][x][t]; else ans+=b[1][x][t]; } return ans; } static int orientation(int k) { //l llr llrllrr goes on and on //we need to find the value at ith index if(k==1) return 0; long p2=1; while(p2<k) p2=p2*2+1; long ex=p2-k,prev=(p2-1)/2; if(prev+1==k) return 0; //this means it was used to attach 2 strings(indices 1,2,4,8,...) return 1^orientation((int)ex+1); //1^ because it means it has been reversed } }