結果
問題 | No.670 log は定数 |
ユーザー |
![]() |
提出日時 | 2018-03-23 23:50:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,812 bytes |
コンパイル時間 | 2,429 ms |
コンパイル使用メモリ | 205,380 KB |
最終ジャッジ日時 | 2025-01-05 09:26:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 10 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;template< typename T >struct RadixHeap{using uint = unsigned;vector< pair< uint, T > > v[32];uint size, last;RadixHeap() : size(0), last(0) {}bool empty() const { return size == 0; }inline int getbit(uint a){return a ? 32 - __builtin_clz(a) : 0;}void push(uint key, const T &value){++size;v[getbit(key ^ last)].emplace_back(key, value);}pair< uint, T > pop(){if(v[0].empty()) {int idx = 1;while(v[idx].empty()) ++idx;last = min_element(begin(v[idx]), end(v[idx]))->first;for(auto &p : v[idx]) v[getbit(p.first ^ last)].emplace_back(p);v[idx].clear();}--size;auto ret = v[0].back();v[0].pop_back();return ret;}};ull seed;inline int next() {seed = seed ^ (seed << 13);seed = seed ^ (seed >> 7);seed = seed ^ (seed << 17);return (seed >> 33);}int main() {int n, q;cin >> n >> q >> seed;for (int i = 0; i < 10000; i++) next();vector<int> a(n);for (int i = 0; i < n; i++) a[i] = next();sort(begin(a), end(a));a.push_back(INT_MAX);ll sm = 0;RadixHeap< int > rad;int last = 0;for (int i = 0; i < q; i++) {if(i - last >= 500000) {int ptr = 0;for(int j = last; j < i; j++) {auto p = rad.pop();while(a[ptr] < p.first) ++ptr;sm ^= ll(ptr) * p.second;}last = i;rad.last = 0;}rad.push(next(), i);}int ptr = 0;for(int j = last; j < q; j++) {auto p = rad.pop();while(a[ptr] < p.first) ++ptr;sm ^= ll(ptr) * p.second;}rad.last = 0;cout << sm << endl;}