fork download
copy 
  1. #include<bits/stdc++.h>
  2. // #pragma GCC optimize("Ofast,no-stack-protector")
  3. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  4. using namespace std;
  5. #define ll long long
  6. int rangeOR(int &l , int &r, vector<vector<int>> &cnt)
  7. {
  8.     int ans = 0;
  9.     for(int i = 0 ; i < 20 ; i++)
  10.     {
  11.         if(cnt[i][r] - cnt[i][l - 1]  > 0)
  12.             ans|=(1<<i);
  13.     }
  14.     return ans;
  15. }
  16. void run_case()
  17. {
  18.     int n ;
  19.     cin>>n ;
  20.     vector<ll> a(n + 1) ;
  21.     vector<int> b(n + 1);
  22.     vector<vector<int>> cnt(20 , vector<int>(n + 1));
  23.     for(int i = 1 ; i <= n ; i++)
  24.     {
  25.         cin>>a[i];
  26.         a[i]*=a[i];
  27.         a[i]+=a[i - 1];
  28.     }
  29.     for(int i = 1 ; i <= n; i++)
  30.     {
  31.         for(int j = 0 ; j < 20 ; j++)
  32.         {
  33.             cnt[j][i] = cnt[j][i - 1];
  34.         }
  35.         cin>>b[i];
  36.         for(int j = 0 ; j < 20 ; j++)
  37.         {
  38.             if((1<<j) & b[i])
  39.             {
  40.                 cnt[j][i]++;
  41.             }
  42.         }
  43.     }
  44.     ll ans = 0;
  45.     vector<vector<int>> pre(20 , vector<int>(n + 1));
  46.     for(int i = 1 ;i <= n ;i++)
  47.     {
  48.         for(int j = 0 ; j < 20 ; j++)
  49.         {
  50.             pre[j][i] = upper_bound(cnt[j].begin() + i , cnt[j].end() , cnt[j][i - 1]) - cnt[j].begin() - 1;
  51.         }
  52.     }
  53.     for(int i = 1 ; i <= n ; i++)
  54.     {
  55.         int cur = i;
  56.         while(cur <= n)
  57.         {
  58.             ll val = rangeOR(i , cur , cnt);
  59.             int lo = n;
  60.             for(int j = 0 ; j <20 ;j ++)
  61.             {
  62.                 if((1<<j) & val)
  63.                     continue;
  64.                 lo = min(lo , pre[j][i]);
  65.             }
  66.             ans+=lower_bound(a.begin() + cur , a.begin() + lo + 1 , a[i - 1] + val*val)-(a.begin() + cur);
  67.             cur = lo + 1;
  68.         }
  69.     }
  70.     cout<<ans<<'\n';
  71. }
  72. signed main()
  73. {
  74.     ios::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     cout.tie(0);
  77.     int t = 1;
  78.     // cin>>t;
  79.     while (t--)
  80.     {
  81.         run_case();
  82.     }
  83.  
  84. }
Runtime error #stdin #stdout #stderr 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Xj6u5M
language:
C++14 (gcc 8.3)
created:
87 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!