結果
問題 | No.619 CardShuffle |
ユーザー | 夕叢霧香(ゆうむらきりか) |
提出日時 | 2017-12-19 01:10:02 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 911 ms / 3,000 ms |
コード長 | 4,160 bytes |
コンパイル時間 | 2,555 ms |
コンパイル使用メモリ | 74,212 KB |
実行使用メモリ | 109,572 KB |
最終ジャッジ日時 | 2023-08-24 14:10:16 |
合計ジャッジ時間 | 21,391 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 118 ms
75,508 KB |
testcase_01 | AC | 126 ms
75,308 KB |
testcase_02 | AC | 129 ms
75,520 KB |
testcase_03 | AC | 128 ms
75,520 KB |
testcase_04 | AC | 125 ms
75,468 KB |
testcase_05 | AC | 130 ms
75,420 KB |
testcase_06 | AC | 128 ms
75,448 KB |
testcase_07 | AC | 129 ms
75,424 KB |
testcase_08 | AC | 128 ms
75,352 KB |
testcase_09 | AC | 126 ms
75,672 KB |
testcase_10 | AC | 123 ms
75,224 KB |
testcase_11 | AC | 123 ms
75,688 KB |
testcase_12 | AC | 127 ms
75,440 KB |
testcase_13 | AC | 128 ms
75,228 KB |
testcase_14 | AC | 126 ms
75,492 KB |
testcase_15 | AC | 126 ms
75,516 KB |
testcase_16 | AC | 824 ms
103,708 KB |
testcase_17 | AC | 832 ms
107,264 KB |
testcase_18 | AC | 911 ms
107,312 KB |
testcase_19 | AC | 807 ms
108,716 KB |
testcase_20 | AC | 868 ms
109,572 KB |
testcase_21 | AC | 726 ms
97,840 KB |
testcase_22 | AC | 751 ms
103,808 KB |
testcase_23 | AC | 775 ms
102,792 KB |
testcase_24 | AC | 755 ms
104,516 KB |
testcase_25 | AC | 713 ms
102,188 KB |
testcase_26 | AC | 836 ms
102,820 KB |
testcase_27 | AC | 837 ms
104,936 KB |
testcase_28 | AC | 831 ms
101,752 KB |
testcase_29 | AC | 844 ms
103,760 KB |
testcase_30 | AC | 787 ms
99,824 KB |
testcase_31 | AC | 117 ms
75,340 KB |
testcase_32 | AC | 782 ms
101,896 KB |
testcase_33 | AC | 821 ms
103,404 KB |
testcase_34 | AC | 782 ms
102,124 KB |
testcase_35 | AC | 488 ms
95,944 KB |
ソースコード
import java.io.*; import java.util.*; class Main { static final long MOD=1000000007; static int[]c,o; static SegmentTree seg; static void update(int i){ if(o[i]==1) seg.update(i,new long[]{-1,0,c[i]}); else seg.update(i,new long[]{c[i],0,1}); } public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out)); int n=sc.nextInt(); c=new int[n/2+1]; o=new int[n/2+1]; for(int i=0;i<n;++i) if(i%2==0) c[i/2]=sc.nextInt(); else o[i/2]=sc.next().equals("*")?1:0; o[n/2]=0; int q=sc.nextInt(); seg=new SegmentTree(); for(int i=0;i<n/2+1;++i)update(i); for(int i=0;i<q;++i){ String t=sc.next(); int x=sc.nextInt(); int y=sc.nextInt(); if(t.equals("!")){ x--; y--; if(x%2==1){ int temp=o[x/2]; o[x/2]=o[y/2]; o[y/2]=temp; }else{ int taplis=c[x/2]; c[x/2]=c[y/2]; c[y/2]=taplis; } update(x/2); update(y/2); }else{ long[]res=seg.query(x/2,y/2+1); long ans=0; if(res[0]>=0) for(int j=0;j<2;++j)ans=(ans+res[j])%MOD; if(o[y/2]==1) ans=(ans+res[2])%MOD; out.println(ans); } } out.close(); } // http://codeforces.com/blog/entry/7018 //-----------PrintWriter for faster output--------------------------------- public static PrintWriter out; //-----------MyScanner class for faster input---------- public static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine(){ String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } } class SegmentTree { static final int SIZE = 1 << 18; static final long MOD=1000000007; long[][] seg; SegmentTree() { this.seg = new long[2 * SIZE][3]; for(int i=0;i<2*SIZE;++i){ seg[i][0]=-1; seg[i][2]=1; } } static long[]comb(long[]a,long[]b){ if(a[0]==-1&&b[0]==-1) return new long[]{-1,0,a[2]*b[2]%MOD}; if(a[0]==-1&&b[0]>=0) return new long[]{a[2]*b[0]%MOD,b[1],b[2]}; if(a[0]>=0&&b[0]==-1) return new long[]{a[0],a[1],a[2]*b[2]%MOD}; return new long[]{a[0],(a[1]+b[1]+a[2]*b[0])%MOD,b[2]}; } void update(int x, long[]value) { x += SIZE - 1; for(int i=0;i<3;++i) this.seg[x][i] = value[i]; while (x > 0) { x = (x - 1) / 2; this.seg[x] = comb(this.seg[2 * x + 1], this.seg[2 * x + 2]); } } long[]query(int a,int b,int l,int r,int k){ if(a<=l&&r<=b)return seg[k]; if(b<=l||r<=a) return new long[]{-1,0,1}; long[]ans1=query(a,b,l,(l+r)/2,2*k+1); long[]ans2=query(a,b,(l+r)/2,r,2*k+2); return comb(ans1,ans2); } long[]query(int l, int r) { return query(l,r,0,SIZE,0); } }