結果
問題 | No.2300 Substring OR Sum |
ユーザー |
|
提出日時 | 2023-07-06 18:26:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 1,657 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 104,280 KB |
最終ジャッジ日時 | 2025-02-15 06:23:28 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<ll,ll> P; typedef pair<int,P> PP; const ll MOD=998244353; const double PI=acos(-1); ll mod_pow(ll x,ll y,ll mod){ ll power=x; ll ret = 1; while(y>0){ if(y&1){ ret = ret*power%mod; } power = power*power%mod; y = y>>1; } return ret; } int main() { int N; cin>>N; vector<int> A(N+1); for(int i=1;i<=N;i++){ cin>>A[i]; } vector<vector<int>> d(30); for(int k=0;k<30;k++){ d[k].push_back(0); for(int i=1;i<=N;i++){ if(((A[i]>>k)&1)==1){ d[k].push_back(i); } } d[k].push_back(N+1); } vector<ll> pow2(30,0); pow2[0]=1; for(int i=1;i<30;i++){ pow2[i]=pow2[i-1]*2; } auto f=[&](ll len){ ll res=1LL*len; res*=(len+1); res/=2; return res; }; ll ans=0; for(int k=0;k<30;k++){ ll sumrange=f(N); for(int j=0;j+1<d[k].size();j++){ int c1=d[k][j]+1; int c2=d[k][j+1]-1; //(d[k][j],d[k][j+1])=[ d[k][j]+1,d[k][j+1]-1]=[c1,c2] if(c1>c2) continue; int len=c2-c1+1; ll range=f(len); sumrange-=range; } //cout<<"k="<<k<<",sumrange="<<sumrange<<endl; ans+=sumrange*pow2[k]; } cout<<ans<<endl; }