結果
問題 | No.1891 Static Xor Range Composite Query |
ユーザー | 37zigen |
提出日時 | 2022-04-04 20:44:43 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,739 ms / 5,000 ms |
コード長 | 5,420 bytes |
コンパイル時間 | 2,726 ms |
コンパイル使用メモリ | 81,124 KB |
実行使用メモリ | 96,280 KB |
最終ジャッジ日時 | 2024-05-04 06:03:52 |
合計ジャッジ時間 | 27,657 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 129 ms
71,248 KB |
testcase_01 | AC | 218 ms
71,480 KB |
testcase_02 | AC | 168 ms
71,232 KB |
testcase_03 | AC | 163 ms
71,548 KB |
testcase_04 | AC | 168 ms
71,380 KB |
testcase_05 | AC | 164 ms
71,464 KB |
testcase_06 | AC | 164 ms
71,572 KB |
testcase_07 | AC | 166 ms
71,188 KB |
testcase_08 | AC | 167 ms
71,500 KB |
testcase_09 | AC | 170 ms
71,504 KB |
testcase_10 | AC | 175 ms
71,516 KB |
testcase_11 | AC | 237 ms
72,308 KB |
testcase_12 | AC | 229 ms
72,024 KB |
testcase_13 | AC | 235 ms
71,988 KB |
testcase_14 | AC | 239 ms
72,056 KB |
testcase_15 | AC | 228 ms
72,024 KB |
testcase_16 | AC | 259 ms
71,932 KB |
testcase_17 | AC | 230 ms
72,176 KB |
testcase_18 | AC | 270 ms
72,076 KB |
testcase_19 | AC | 226 ms
72,136 KB |
testcase_20 | AC | 220 ms
72,152 KB |
testcase_21 | AC | 1,667 ms
94,392 KB |
testcase_22 | AC | 1,634 ms
84,792 KB |
testcase_23 | AC | 1,739 ms
94,384 KB |
testcase_24 | AC | 1,660 ms
84,680 KB |
testcase_25 | AC | 1,572 ms
94,288 KB |
testcase_26 | AC | 1,602 ms
96,280 KB |
testcase_27 | AC | 1,506 ms
84,420 KB |
testcase_28 | AC | 1,683 ms
94,328 KB |
testcase_29 | AC | 1,571 ms
84,568 KB |
testcase_30 | AC | 1,631 ms
94,460 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.NoSuchElementException; public class Main implements Runnable { //Runnableを実装する public static void main(String[] args) { new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); //16MBスタックを確保して実行 } public void run() { solve(); } final long mod=998244353; class Query implements Comparable<Query> { int l; int r; int p; long x; int id; public Query(int l, int r, int p, long x, int id) { this.l=l; this.r=r; this.p=p; this.x=x; this.id=id; } int reverseOrder() { int b=0; for (int i=17;i>=0;--i) { b|=((p>>i)%2)<<(17-i); } return b; } @Override public int compareTo(Main.Query o) { return Integer.compare(reverseOrder(), o.reverseOrder()); } } class SegTree { long[] a; long[] b; int[] l_pointer; int[] r_pointer; int n=1<<18; public SegTree(int n_, long[] a_, long[] b_) { a=new long[2*n-1]; b=new long[2*n-1]; l_pointer=new int[2*n-1]; r_pointer=new int[2*n-1]; Arrays.fill(a, 1); for (int i=0;i<n_;++i) { a[i+n-1]=a_[i]; b[i+n-1]=b_[i]; } for (int i=n-2;i>=0;--i) { long[] ab=merge(a[2*i+1], b[2*i+1], a[2*i+2], b[2*i+2]); a[i]=ab[0]; b[i]=ab[1]; l_pointer[i]=2*i+1; r_pointer[i]=2*i+2; } } long[] merge(long al, long bl, long ar, long br) { return new long[] {ar*al%mod, (ar*bl+br)%mod}; } long[] query(int l, int r, int L, int R, int k) { if (r <= L || R <= l) return new long[] {1, 0}; if (L <= l && r <= R) return new long[] {a[k], b[k]}; long[] vl=query(l, (l+r)/2, L, R, l_pointer[k]); long[] vr=query((l+r)/2, r, L, R, r_pointer[k]); return merge(vl[0], vl[1], vr[0], vr[1]); } // 0-indexed // 下から bit 目 void swap(int bit) { bit=17-bit; for (int i=0;i<(1<<bit);++i) { int k=(1<<bit)-1+i; l_pointer[k]^=r_pointer[k];r_pointer[k]^=l_pointer[k];l_pointer[k]^=r_pointer[k]; } for (int i=(1<<(bit+1))-2;i>=0;--i) { long[] ab=merge(a[l_pointer[i]], b[l_pointer[i]], a[r_pointer[i]], b[r_pointer[i]]); a[i]=ab[0]; b[i]=ab[1]; } } long eval(int L, int R, long x) { long[] ab=query(0, n, L, R, 0); return (ab[0]*x+ab[1])%mod; } } public void solve() { FastScanner sc=new FastScanner(); PrintWriter pw=new PrintWriter(System.out); int N=sc.nextInt(); int Q=sc.nextInt(); long[] A=new long[N]; long[] B=new long[N]; for (int i=0;i<N;++i) { A[i]=sc.nextLong(); B[i]=sc.nextLong(); } SegTree tree=new SegTree(N, A, B); int mask=0; ArrayList<Query> list=new ArrayList<>(); for (int i=0;i<Q;++i) { int l=sc.nextInt(); int r=sc.nextInt(); int p=sc.nextInt(); long x=sc.nextLong(); list.add(new Query(l, r, p, x, i)); } Collections.sort(list); long[] ans=new long[Q]; for (int i=0;i<Q;++i) { Query query=list.get(i); int xor=mask^query.p; for (int shift=0;shift<18;++shift) { if ((xor>>shift)%2==1) { tree.swap(shift); mask^=1<<shift; } } ans[query.id]=tree.eval(query.l, query.r, query.x); } for (int i=0;i<Q;++i) { pw.println(ans[i]); } pw.close(); } static void tr(Object...objects) { System.out.println(Arrays.deepToString(objects)); } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int)nextLong(); } }