Poj Solution 1810

http://poj.org/problem?id=1810

#include<iostream>
#include"algorithm"
using std::sort;
using namespace std;
int s[1001],N,K,M;
long d[10000];


int max()
{int i,k=M;
for(i=M+1;i<=N;i++)if(s[k]<=s[i])k=i;
return k;
}

void find()
{int i,j,k,h,down,up,x=N,y=N,best=0;
    
    for(i=N,j=0,h=0;i>=M;i--)
    {while(h<j&&d[h]%2000>i)
        {down=d[h]/2000;up=down+M-1<N?down+M-1:N;
        for(k=down;k<=up;k++)s[k]--;
        h++;
        }
    while(j<K&&i-d[j]%2000<M)
        {down=d[j]/2000;up=down+M-1<N?down+M-1:N;
        for(k=down;k<=up;k++)s[k]++;
        j++;
        }
    k=max();
    if(s[k]>best){best=s[k];y=k;x=i;}
    if(j>=K)break;
    }
    cout<<x-M<<' '<<y-M<<endl;
}
int cmp(long a,long b)
{return a%2000>b%2000;}

int main()
{int t,i;double a,b;
cin>>t;
while(t--)
{cin>>K>>N>>M;
for(i=0;i<K;i++){cin>>a>>b;d[i]=(long(a)+1)+2000*(long(b)+1);}

sort(&d[0],&d[K],cmp);
for(i=0;i<=N;i++)s[i]=0;
find();
}
return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *