Problem : Sliding Window Or
I am getting a TLE in this problem. This is my code:
// HELPPP...
#include<bits/stdc++.h>
using namespace std;
vector<long long> v, ors;
int main(){
int n , k; cin >> n >> k;
int x , a , b , c; cin >> x >> a >> b >> c;
long long p = x;
for(long long i = 1; i <= n; ++i){
v.push_back(p);
p = ( a * p + b ) % c;
}
long long ori = 0;
vector<int> bits(32);
for(int i= 0 ; i < k; ++i){
ori |= v[i];
for(int j = 0 ; j < 32; ++j ){
if(v[i]&(1LL<<j))bits[j]++;
}
}
ors.push_back(ori);
for(int i = k; i < n; ++i){
ori |= v[i];
for(int j = 0 ; j < 32; ++j){
if(v[i]&(1LL<<j))
bits[j]++;
}
for(int j = 0 ; j < 32; ++j){
if(v[i-k]&(1LL<<j)){
bits[j]--;
if(!bits[j]) ori -= (1LL<<j);
}
}
ors.push_back(ori);
}
long long ans = 0;
for(auto i : ors)
ans ^= i;
cout << ans << endl;
}
How can i avoid the inner 32 loops in for loop ? or is there any other way to do it ?
32*1e7 operations can only be done if you don't access memory. Calculate element, compute bits time to live, and don't save anything else. Without any tricks it runs in 0.3-0.4 CSES seconds, with a little trickery my solution runs in 0.25 sec (currently #3 in statistics).
thanks but can i can't think of anything other than using the bits(32) vector and storing every bits of the numbers :(
I explained the idea here https://mirror.codeforces.com/blog/entry/142846#comment-1275165
you can refer this solution prefix suffix approach !!
There exists a linear solution using monotonic deque (or whatever it is called). The structure allows maintaining any associative operation with an identity element — i.e., any monoid operation on the window.
This is only the interface of a queue though. To make it a deque, when popping
frontandfrontis empty you move half of the elements frombacktofrontinstead, same for poppingback. This gives armotized $$$O(1)$$$ per operation.Read more here [Tutorial] Minimum Deque.
Almost entire sliding window section can be solved using this same code with this, but what's the point, isn't it more fun to think of different solution?