結果
問題 | No.670 log は定数 |
ユーザー |
![]() |
提出日時 | 2017-09-11 21:42:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,640 ms / 4,000 ms |
コード長 | 1,211 bytes |
コンパイル時間 | 1,457 ms |
コンパイル使用メモリ | 162,920 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-11-07 17:07:03 |
合計ジャッジ時間 | 19,769 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)#define rep1(i,n) for(int i=1;i<=(int)(n);i++)#define all(c) c.begin(),c.end()#define pb push_back#define fs first#define sc second#define show(x) cout << #x << " = " << x << endl#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)using namespace std;template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}using ull = unsigned long long;using ll = long long;ull seed;int next(){seed = seed ^ (seed<<13);seed = seed ^ (seed>>7);seed = seed ^ (seed<<17);return (seed>>33);}const int X = 17;const int B = 1<<X;vector<int> a[B];int acc[B+1];int main(){int N,Q;cin>>N>>Q>>seed;rep(i,10000) next();rep(i,N){int x = next();a[x>>(31-X)].pb(x);}rep(i,B) sort(all(a[i]));rep(i,B) acc[i+1] = acc[i] + a[i].size();ll res = 0;rep(qt,Q){int x = next();int b = x>>(31-X);int cnt = acc[b] + lower_bound(all(a[b]),x) - a[b].begin();res ^= ll(cnt)*qt;}cout<<res<<endl;}