# TLE in Spoj Question DCEPC705

Hi guys, I am stuck in this problem: http://www.spoj.com/problems/DCEPC705/
I am unable to find a better way to solve this problem as a result I am getting TLE. It would be very helpful if anyone can help My solution(thatâ€™s what I tried, pretty naive solution) -> Solution

1 Like

Brother, try this in any version of C++ compiler(s),
Run time is O(n log^3 n).

``````#include<cstdio>
#include<algorithm>
#include<tr1/unordered_map>
#include<map>
#include<cstdlib>
const int MAXN=100001;
typedef std::pair<int,int> pii;
inline int getNum()
{
int res=0;
char c;
while(1) {
c=getchar_unlocked();
if(c<'0'||c>'9') continue;
else break;
}
res=c-'0';
while(1) {
c=getchar_unlocked();
if(c>='0' && c<='9') res=(res<<3)+(res<<1)+c-'0';
else break;
}
return res;
}

pii T[MAXN];
int n,test,a,b,k,cor[2*MAXN+10],whur,id;

std::tr1::unordered_map<int,int> Tree[MAXN*2];
std::map<int,int> New_id;

void Update(int x,int yy)
{
for(;x<id;x+=(x&-x))
for(int y=yy;y<id;y+=(y&-y))
++Tree[x][y];
}
int Get(int x,int yy)
{
int res=0;
for(;x;x-=(x&-x))
for(int y=yy;y;y-=(y&-y))
res+=Tree[x][y];
return res;
}

int main(void)
{
test=getNum();
while(test--)
{
whur=0;id=1;
for(int i=0;i<=n;++i)
Tree[i].clear();
n=getNum();k=getNum();
for(int i=0;i<n;++i)
scanf("%d%d",&T[i].first,&T[i].second), cor[whur++]=T[i].first, cor[whur++]=T[i].second;
std::sort(cor,cor+whur);
cor[whur]=-2000000000;
for(int i=1;i<=whur;++i)
if(cor[i-1]!=cor[i])New_id[cor[i-1]]=id++;

for(int i=0;i<n;++i)
T[i].first=New_id[T[i].first], T[i].second=New_id[T[i].second];

for(int i=0;i<n;++i)
Update(T[i].first,T[i].second);

int ans=0,tmp;
for(int i=0;i<n;++i){
tmp=Get(T[i].first,T[i].second)-1;
if(abs(n-1-2*tmp)>=k)++ans;
}
printf("%d\n",ans);
}
return 0;
}``````
2 Likes

Dude, thanks for the code but I want to know the logic part only. I want to code it myself so that I learn Can you explain what you did?

2 Likes

Problem gives us N points with coords up to 10^9
For each point we have to calculate two values : d_i and n_i
First is about dominating other points.
Point i dominates point j if x_i >= x_j and y_i >= y_j

And n_i = n-1-d_i

we have to answer how many points are ok with
|d_i - n_i|>=k
For some given k.

Dude I know the question. I want to know your approach in solving this question.

2 Likes