set<int>s;
for(int i=0;i<20000;++i)
{
s.insert(i+i%1113);
auto it = upper_bound(s.begin(),s.end(),i-1);
it = lower_bound(s.begin(),s.end(),i-1);
}
This code does what you are doing - inserting into a set once, finding upper bound once, and lower bound once, 20000 times. This takes 6.5 seconds on my machine (which I believe is only a little slower than SPOJ tester). It takes 15 seconds for upper limit of 30000. The problem has cases with n=10^5, likely multiple cases in one file such as this. So you will surely get TLE.
By removing the upper_bound and lower_bound, it runs in 0.05 seconds.
TL;DR: upper_bound and lower_bound are VERY slow. If you can avoid their use, always do so. I'm not promising you will get AC if you remove them, but with these functions it is hopeless even with correct complexity.