fork download
copy 
  1. #pragma GCC optimization ("unroll-loops")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
  4. //based on blog about count A[i] & A[j] = 0
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. const int N = 100002 /** enough?! **/, K = 30, L = 10, MOD = 1000000007;
  10.  
  11. void solve() {
  12.     int n = 8;
  13.     scanf("%d", &n);
  14.     vector <int> a(n);
  15.     vector <bitset <N> > bit(K);
  16.     vector <vector <bitset <N> > > pre(K/L+1, vector <bitset<N> > (1 << L));
  17.     //for (int i = 0; i < K; ++i) {
  18.     //    bit[i].reset();
  19.     //}
  20.     for (int i = 0; i < n; ++i) {
  21.        // a[i] = i + 1;
  22.         scanf("%d", &a[i]);
  23.         for (int b = 0; b < K; ++b) {
  24.             if ((a[i] >> b) & 1) {
  25.                 bit[b].set(i);
  26.             }
  27.         }
  28.     }
  29.     vector <int> idx(1 << L, -1);
  30.     for (int i = 0; i < L; ++i) {
  31.         idx[1 << i] = i;
  32.     }
  33.     for (int i = 0; i < K; i += L) {
  34.         int S = i, E = min(K, i + L);
  35.         for (int j = 1; j < 1 << (E - S); ++j) {
  36.             //assert (idx[j & -j] != -1);
  37.             pre[i / L][j] = pre[i / L][j - (j & -j)] | bit[S + idx[j & -j]];
  38.            /* for (int k = 0; k < E - S; ++k) {
  39.                 if (j & (1 << k)) {
  40.                     pre[i / L][j] |= bit[S + k];
  41.                 }
  42.             }*/
  43.         }
  44.     }
  45.     long long what = 0;
  46.     for (int w = 0; w < n; ++w) {
  47.         bitset <N> cur;
  48.         for (int i = 0; i < K; i += L) {
  49.             cur |= pre[i / L][(a[w] >> i) & ((1 << L) - 1)];
  50.         }
  51.         what += n - cur.count();
  52.     }
  53.     cout << what / 2 << '\n'; //can get rid of /2 by updating pre online and check bitsets till w-th index, but that does not really improve
  54.     return;
  55.     //O(N*D/L*N/Word+2^L*N/Word*(D/L)) -> L = 10 -> 512*10^5
  56.     if (0) { int ans = 0, tmp = 0;
  57.     for (int i = 0; i < n; ++i) {
  58.         bitset <N> all;
  59.         for (int b = 0; b < K; ++b) { //b += L
  60.             if ((a[i] >> b) & 1) {
  61.                 all |= bit[b];
  62.             }
  63.         }
  64.         tmp += n - all.count();
  65.         for (int j = i + 1; j < n; ++j) {
  66.             if ((a[i] & a[j]) == 0) {
  67.                 ++ans;
  68.             }
  69.         }
  70.     }
  71.     cout << ' ' << ans << ' ' << tmp / 2 << '\n'; }
  72. }
  73.  
  74. int main() {
  75. //    freopen("input.txt", "r", stdin);
  76. //    freopen("ipn.inp", "r", stdin); freopen("ipn.out", "w", stdout);
  77. //    ios::sync_with_stdio(false); cin.tie(0);
  78.     int t = 1;
  79.     //scanf("%d", &t);
  80.     while (t --> 0) {
  81.         solve();
  82.     }
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0.03s 66260KB
comments (?)
stdin
copy 
8
1 2 3 4 5 6 7 8
stdout
copy 
13
https://ideone.com/SN2Bfz
language:
C++14 (gcc 8.3)
created:
231 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!