結果
問題 | No.670 log は定数 |
ユーザー |
👑 |
提出日時 | 2019-01-25 00:05:31 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 3,253 ms / 4,000 ms |
コード長 | 3,135 bytes |
コンパイル時間 | 1,011 ms |
コンパイル使用メモリ | 123,904 KB |
実行使用メモリ | 22,760 KB |
最終ジャッジ日時 | 2024-06-13 03:40:54 |
合計ジャッジ時間 | 16,777 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
import std.conv, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp)>> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }/********/ulong seed;int next() {seed = seed ^ (seed << 13);seed = seed ^ (seed >> 7);seed = seed ^ (seed << 17);return cast(int)(seed >> 33);}/********/enum L = 10^^6;int N, Q;int[] A;void main() {try {for (; ; ) {N = readInt();Q = readInt();seed = readLong();foreach (i; 0 .. 10000) {next();}A = new int[N];foreach (i; 0 .. N) {A[i] = next();}debug {writeln("A = ", A[0 .. min(10, $)]);}A.sort;auto xs = new int[L];auto js = new int[L];auto work = new int[L];auto buckets = new int[0x10001];auto ans = new int[L];long ansSum;for (int qL = 0; qL < Q; qL += L) {const qR = min(qL + L, Q);foreach (q; qL .. qR) {xs[q - qL] = next();}const len = qR - qL;debug {if (qL / L < 10) {writeln("queries ", xs[0 .. min(len, 10)]);}}foreach (j; 0 .. len) {js[j] = j;}// radix sortbuckets[] = 0;foreach (j; 0 .. len) ++buckets[(xs[js[j]] & 0xffff) + 1];foreach (h; 0 .. 0x10000) buckets[h + 1] += buckets[h];foreach (j; 0 .. len) work[buckets[xs[js[j]] & 0xffff]++] = js[j];buckets[] = 0;foreach (j; 0 .. len) ++buckets[(xs[work[j]] >> 16) + 1];foreach (h; 0 .. 0x10000) buckets[h + 1] += buckets[h];foreach (j; 0 .. len) js[buckets[xs[work[j]] >> 16]++] = work[j];debug {if (qL / L < 10) {writeln("js = ", js[0 .. min(len, 10)]);}}for (int i = 0, j = 0; j < len; ++j) {for (; i < N && A[i] < xs[js[j]]; ++i) {}ans[js[j]] = i;}foreach (q; qL .. qR) {ansSum ^= cast(long)(ans[q - qL]) * q;}}writeln(ansSum);}} catch (EOFException e) {}}