Getting TLE plz help

Revision en1, by tasirmoon, 2022-12-15 16:25:50

//https://www.codechef.com/problems-old/LONGESTARRAY

include <bits/stdc++.h>

using namespace std; typedef long long ll; typedef vector vll; ll n; bool ok(vll v, ll now, vll &ar) { vll v1(35, 0); ll x = 0; for (ll i = 1; i < now; ++i) { for (ll j = 0; j < 32; ++j) { if (ar[i] & (1ll << j)) v1[j]++, v[j]--; } } for (ll i = now; i <= n; ++i) { x = 0; for (ll j = 0; j < 31; ++j) { if (ar[i] & (1ll << j)) v1[j]++, v[j]--; if ((i — now > 0) && (ar[i — now] & (1ll << j))) v1[j]--, v[j]++; if ((v[j] == 0 && v1[j]) || (v1[j] == 0 && v[j])) x++; } // cout << now << nn; // cout << x << nn; if (!x) return 1; } return 0; } int main() { ll t; scanf("%lld", &t); for (ll ts = 1; ts <= t; ++ts) {

scanf("%lld", &n);
    vll ar(n + 1);
    vll v(35, 0);
    for (ll i = 1; i <= n; ++i)
    {
        scanf("%lld", &ar[i]);
        ll x = ar[i];
        for (int j = 0; j < 32; ++j)
            if (x & (1ll << j))
                v[j]++;
    }
    ll left = 1, right = n, ans = -1;
    while (left <= right)
    {
        ll mid = (left + right) / 2;
        if (ok(v, mid, ar))
        {
            ans = max(mid, ans);
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    printf("%lld\n", ans);
}
return 0;

}

I am getting TLE 1.0100ms .can anyone help me to optimize the solution??

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English tasirmoon 2022-12-15 16:26:38 1631
en1 English tasirmoon 2022-12-15 16:25:50 1788 Initial revision (published)