I am adding my code here. I ahve MO algorithm along with scanf/printf still getting TLE. Can anyone please help.
include
using namespace std;
include
include
include
include
include
int n;
bool myComparison(const pair &a,const pair &b)
{
if(ceil(a.first/sqrt(n)) == ceil(b.first/sqrt(n)))
return a.second else
return ceil(a.first/sqrt(n))}
int main() {
// your code goes here
int i=0;
//int block_size=sqrt(n);
//map b;
//i=1+b;
vector val;
long c[300003];
vector> dq;
vector> dq2;
vector>:: iterator it2,it3;
vector v;
vector:: iterator it;
scanf("%d",&n);
//printf("%d",n);
int temp=n;
while(temp--)
{
long l;
scanf("%ld",&l);
val.push_back(l);
//printf("%ld ",l);
}
int q,q1,q2;
scanf("%d",&q);
//printf("\n%d\n",q);
temp=q;
while(temp--)
{
scanf("%d%d",&q1,&q2);
dq.emplace_back(q1-1,q2-1);
dq2.emplace_back(q1,q2);
c[temp]=0;
//printf(" %d %d ",q1-1,q2-1);
}
sort(dq.begin(),dq.end(),myComparison);
int mo_left=0,mo_right=0,count=0,flag=0;
for(i=0;i {
// printf("dq[i].first=%d dq[i].second=%d\n",dq[i].first,dq[i].second);
if(mo_right<=dq[i].second)
{
while(mo_right {
if(find(v.begin(),v.end(),val[mo_right])==v.end())
{
count++;
// printf("element added=%ld mo_right=%d\n",val[mo_right],mo_right);
v.push_back(val[mo_right]);
mo_right++;
}
else
mo_right++;
}
if(find(v.begin(),v.end(),val[mo_right])==v.end())
{
count++;
// printf("element added=%ld mo_right=%d\n",val[mo_right],mo_right);
v.push_back(val[mo_right]);
}
}
else
{
while(mo_right>dq[i].second)
{
it=find(val.begin()+dq[i].first,val.begin()+dq[i].second+1,val[mo_right]);
// printf("val[it]=%ld val[mo_right]=%ld\n",val[it-val.begin()],val[mo_right]);
if(it==val.begin()+dq[i].second+1)
{
it=find(v.begin(),v.end(),val[mo_right]);
if(it!=v.end())
{
count--;
// printf("Element Removed=%ld mo_right=%d\n",val[mo_right],mo_right);
mo_right--;
v.erase(it);
}
}
else
mo_right--;
}
if(find(v.begin(),v.end(),val[mo_right])==v.end())
{
count++;
// printf("element added=%ld mo_right=%d\n",val[mo_right],mo_right);
v.push_back(val[mo_right]);
}
}
//printf("mo_left=%d dq[i].first=%d",mo_left,dq[i].first);
if(mo_left<=dq[i].first)
{
while(mo_left<dq[i].first)
{
it=find(val.begin()+dq[i].first,val.begin()+dq[i].second+1,val[mo_left]);
//printf("v[it]=%ld\n",val[it-val.begin()]);
if(it==val.begin()+dq[i].second+1)
{
it=find(v.begin(),v.end(),val[mo_left]);
if(it!=v.end())
{
count--;
//printf("Element Removed=%ld mo_left=%d\n",val[mo_left],mo_left);
v.erase(it);
}
mo_left++;
//printf("mo_left=%d val[mo_left]=%d\n",mo_left,val[mo_left]);
}
else
mo_left++;
}
if(find(v.begin(),v.end(),val[mo_left])==v.end())
{
count++;
//printf("element added=%ld mo_left=%d\n",val[mo_left],mo_left);
v.push_back(val[mo_left]);
}
}
else
{
while(mo_left>dq[i].first)
{
// printf("WHILE 1 val[mo_left]=%ld",val[mo_left]);
if(find(v.begin(),v.end(),val[mo_left])==v.end())
{
count++;
//printf("element added=%ld mo_left=%d\n",val[mo_left],mo_left);
v.push_back(val[mo_left]);
mo_left--;
}
else
mo_left--;
}
if(find(v.begin(),v.end(),val[mo_left])==v.end())
{
count++;
//printf("element added=%ld mo_left=%d\n",val[mo_left],mo_left);
v.push_back(val[mo_left]);
}
}
it2=find(dq2.begin(),dq2.end(),make_pair(dq[i].first+1,dq[i].second+1));
if(c[it2-dq2.begin()]==0)
{
c[it2-dq2.begin()]=count;
//printf("it2-dq2=%d ",it2-dq2.begin());
}
else
{
it3=find(++it2,dq2.end(),make_pair(dq[i].first+1,dq[i].second+1));
//printf("it3-dq2.begin()=%d",it3-dq2.begin());
c[it3-dq2.begin()]=count;
}
//printf("COUNT=%d dq[i].first=%d dq[i].second=%d ",count,dq[i].first+1,dq[i].second+1);
//printf("found pair= %ld %ld %ld",dq2[it2-dq2.begin()].first,dq2[it2-dq2.begin()].second,it2-dq2.begin());
//printf("count=%d mo_left=%d mo_right=%d\n",count,mo_left,mo_right);
}
for(i=0;i<q;i++)
printf("%d\n",c[i]);
return 0;
}