結果
問題 | No.670 log は定数 |
ユーザー |
![]() |
提出日時 | 2017-09-10 03:35:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,575 ms / 4,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 1,382 ms |
コンパイル使用メモリ | 113,760 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-11-07 12:40:38 |
合計ジャッジ時間 | 19,127 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <iostream>#include <iomanip>#include <cstdio>#include <cstdlib>#include <cstring>#include <cassert>#include <algorithm>#include <numeric>#include <random>#include <vector>#include <array>#include <bitset>#include <queue>#include <set>#include <unordered_set>#include <map>#include <unordered_map>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }template<class T> using V = vector<T>;template<class T> using VV = V<V<T>>;ull seed;int next() {seed = seed ^ (seed << 13);seed = seed ^ (seed >> 7);seed = seed ^ (seed << 17);return (seed >> 33);}int n;V<int> a;const ll B = 300000;const ll S = (1LL<<32) / B + 1;V<int> l, r;void first() {l = V<int>(B);r = V<int>(B);int c = 0;for (int i = 0; i < B; i++) {l[i] = c;while (c < n && (a[c] / S) == i) c++;r[i] = c;}}ll query(int x) {int i = x / S;return lower_bound(begin(a) + l[i], begin(a) + r[i], x) - begin(a);}int main() {cin.tie(0);ios::sync_with_stdio(false);cout << setprecision(20);int q;cin >> n >> q >> seed;for (int i = 0; i < 10000; i++) next();a = V<int>(n);for (int i = 0; i < n; i++) a[i] = next();sort(begin(a), end(a));first();ll sm = 0;for (int i = 0; i < q; i++) {int x = next();// sm ^= lower_bound(begin(a), end(a), x) - begin(a) + i;sm ^= query(x) * i;}cout << sm << endl;return 0;}