結果

問題 No.670 log は定数
ユーザー ei1333333ei1333333
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0