TLE in Spoj Question DCEPC705

general
, , ,
1

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 :slight_smile: My solution(that’s what I tried, pretty naive solution) → Solution

1 Like
2

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
3

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

2 Likes
4

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.

5

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

2 Likes