I am trying to solve Multiple of 3 question
I am using 0 based indexing here. But I am getting TLE .
Can anyone help me in figuring out the issue with it.
[MY Code]
(CodeChef: Practical coding for everyone)
#include <bits/stdc++.h>
using namespace std;
int seg[400004][3] ; int lazy[400004];
void bulilSegtree(int index , int low , int high)
{
if (low == high)
{
seg[index][0] = 1;
seg[index][1] = 0;
seg[index][2] = 0;
return;
}
int mid = (low + high) / 2;
bulilSegtree(2 * index + 1, low , mid);
bulilSegtree(2 * index + 2, mid + 1, high);
seg[index][0] = (seg[2 * index + 1][0] + seg[2 * index + 2][0]);
seg[index][1] = (seg[2 * index + 1][1] + seg[2 * index + 2][1]);
seg[index][2] = (seg[2 * index + 1][2] + seg[2 * index + 2][2]);
}
void shift(int index)
{
int temp = seg[index][2];
seg[index][2] = seg[index][1];
seg[index][1] = seg[index][0];
seg[index][0] = temp;
}
int query(int index , int low , int high , int &l , int &r)
{
if (lazy[index] != 0)
{
int dx = lazy[index];
lazy[index] = 0;
if (low != high)
lazy[2 * index + 1] += dx , lazy[2 * index + 2] += dx;
int totalCycle = dx%3;
for(int i=0;i<totalCycle;i++)
shift(index);
}
if (l > high || r < low)
return 0;
if (low >= l && high <= r)
return seg[index][0];
int mid = (low + high) / 2;
int left = query(index * 2 + 1, low, mid, l, r);
int right = query(index * 2 + 2, mid + 1, high, l, r);
return (left + right);
}
void rangeUpdate(int index , int low , int high , int &l , int &r)
{
if (lazy[index] != 0)
{
int dx = lazy[index];
lazy[index] = 0;
if (low != high)
lazy[2 * index + 1] += dx , lazy[2 * index + 2] += dx;
int totalCycle = dx%3;
for(int i=0;i<totalCycle;i++)
shift(index);
}
if (l > high || r < low)
return ;
if (low >= l && high <= r)
{
shift(index);
if (low != high)
lazy[2 * index + 1] += 1 , lazy[2 * index + 2] += 1;
return;
}
int mid = (low + high) / 2;
rangeUpdate(2 * index + 1, low , mid , l , r);
rangeUpdate(2 * index + 2 , mid + 1 , high , l , r);
seg[index][0] = seg[2 * index + 1][0] + seg[2 * index + 2][0];
seg[index][1] = seg[2 * index + 1][1] + seg[2 * index + 2][1];
seg[index][2] = seg[2 * index + 1][2] + seg[2 * index + 2][2];
}
void solveTestCases()
{
int n;
cin>>n;
int q;
cin>>q;
bulilSegtree(0 , 0 , n-1);
while (q--)
{
int type;
cin>>type;
int a , b;
cin>>a>>b;
if(type == 0)
{
rangeUpdate(0,0,n-1,a,b);
}else if(type ==1 )
{
cout<<query(0,0,n-1,a,b)<<endl;
}
}
return;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
solveTestCases ();
return 0;
}