Problem B. Paragliding Google Kickstart Round D 2018

擷取氣球時隻能向下45°滑行而不能向上滑。對于每一個Tower a和氣球b，如果abs(p[a]-x[b])<=h[a]-y[b]則可以取到氣球，小資料直接N^2枚舉即可。

大資料必然是O(N)的，但開始也沒發現什麼類似單調性的規律去減少枚舉。一直在糾結如果離氣球b最近的tower a無法獲得氣球，而更遠的tower c可以獲得氣球a該如何處理，這樣很難減少枚舉上限。><後來得知，這種情況下如果tower a無法取得氣球b，tower a可以被tower b取代，因為如果從tower a可以獲得某個氣球x，從tower b一定可以獲得那個氣球x。（畫個圖就可以很明白滴看出來，tower a的區域包含于tower b的區域中）那麼abs(p[a]-x[b])>h[a]-y[b]，abs(p[c]-x[b])<=h[c]-y[b]，可以得出tower a被tower c替代的條件是abs(p[a]-p[c])<=h[a]-h[c]（畫個圖也可以看出來）

Then，可以先除去多餘的Tower，再對于某一個balloons，找到距離其最近的兩個Tower a, c，如果這兩個Tower無法擷取balloon，更遠的Tower也不可能擷取balloon，否則tower a, c就可以被更遠的Tower替代。

除去多餘的Tower：現将所有的Tower按照p[i]排序，周遊所有的tower i，如果tower i可以被new tower array尾部的tower替代，skip tower i，如果tower i可以替代new tower array尾部的Tower,将new tower array的Tower pop出來直到最後一個Tower不會被tower i替代為止。最後再将tower i append至new tower array尾部。因為Tower覆寫範圍都是45°，不會出現排序後tower i不會替代tower i+1, 卻會替代tower i+2的情況。

遇到的bugs：

計算p[i],h[i],x[i],y[i]時，公式是p[i]=linear(p[i-1],p[i-2])%M+1，是以不等于(linear(p[i-1]%M,p[i-2]%M)+1)%M...之前寫習慣了，過了好久才發現o(╯□╰)o

在一個sorted數組中查找x，如果x不在數組裡面，傳回的mid可能是x插入位置的左邊element下标，也可能是插入位置的右邊element下标，是以mid-1,mid,mid+1都要check。用lower_bound()可以避免這個問題。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<ctype.h>
#include<map>
#include<time.h>
#include<set>
#include<bitset>
#include<sstream>
using namespace std;
//2018 round D Problem B. Paragliding
const int maxn=100010;
int T;
int N;
int K;
long long p[maxn];
long long x[maxn];
long long h[maxn];
long long y[maxn];
long long A[4];
long long B[4];
long long C[4];
long long M[4];
long long ans;
int sorted_tower[maxn];
int relative_tower[maxn];
bool cmp(int a,int b)
{
    return p[a]<p[b];
}
int check_relative(int a,int b)
{
    if(h[a]-h[b]>=abs(p[a]-p[b]))
    {
        return 0; // b is useless
    }
    else if(h[b]-h[a]>=abs(p[a]-p[b]))
    {
        return 1; // a is useless
    }
    else
    {
        return 2; //not relative
    }

}
bool get_ballon(int a,int b)//a is tower, b is ballon
{
//    cout<<"get ballon "<<a<<" "<<b<<" "<<h[a]<<" "<<p[a]<<" "<<y[b]<<" "<<x[b]<<endl;
    if(h[a]-y[b]>=abs(p[a]-x[b]))
    {
        return true;
    }
    return false;
}
int main()
{

    cin>>T;
    for(int ca=1;ca<=T;ca++)
    {
        
        memset(p,0,sizeof(p));
        memset(x,0,sizeof(x));
        memset(h,0,sizeof(h));
        memset(y,0,sizeof(y));
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        memset(M,0,sizeof(M));
        memset(sorted_tower,0,sizeof(sorted_tower));
        memset(relative_tower,0,sizeof(relative_tower));
        ans=0;
        cin>>N>>K;
        cin>>p[0]>>p[1]>>A[0]>>B[0]>>C[0]>>M[0];
        cin>>h[0]>>h[1]>>A[1]>>B[1]>>C[1]>>M[1];
        cin>>x[0]>>x[1]>>A[2]>>B[2]>>C[2]>>M[2];
        cin>>y[0]>>y[1]>>A[3]>>B[3]>>C[3]>>M[3];
        for(int i=2;i<N;i++)
        {
            p[i]=(p[i-1]*A[0]+p[i-2]*B[0]+C[0])%M[0]+1;
            h[i]=(h[i-1]*A[1]+h[i-2]*B[1]+C[1])%M[1]+1;
//            p[i]=p[i-1]*A[0]%M[0]+p[i-2]*B[0]%M[0]+C[0]%M[0]+1;  without mod M at teh end, the value is different
//            p[i]%=M[0]; no need to take mod at the end
//            h[i]=h[i-1]*A[1]%M[1]+h[i-2]*B[1]%M[1]+C[1]%M[1]+1;
//            h[i]%=M[1];
        }
        for(int i=2;i<K;i++)
        {
            x[i]=(x[i-1]*A[2]+x[i-2]*B[2]+C[2])%M[2]+1;
            y[i]=(y[i-1]*A[3]+y[i-2]*B[3]+C[3])%M[3]+1;
//            x[i]=x[i-1]*A[2]%M[2]+x[i-2]*B[2]%M[2]+C[2]%M[2]+1;
//            x[i]%=M[2];
//            y[i]=y[i-1]*A[3]%M[3]+y[i-2]*B[3]%M[3]+C[3]%M[3]+1;
//            y[i]%=M[3];
        }
        for(int i=0;i<N;i++)
        {
            sorted_tower[i]=i;
        }
        sort(sorted_tower,sorted_tower+N,cmp);
//        for(int i=0;i<N;i++)
//        {
//            cout<<"("<<p[i]<<","<<h[i]<<") "<<endl;
//        }
//        cout<<endl;

//        for(int i=0;i<K;i++)
//        {
//            cout<<"("<<x[i]<<","<<y[i]<<") "<<endl;
//        }
//        cout<<endl;
        int cnt=0;
        for(int i=0;i<N;i++)
        {
            if(cnt==0)
            {
                relative_tower[cnt++]=sorted_tower[i];
                continue;
            }
            else
            {
                int check=check_relative(sorted_tower[i],relative_tower[cnt-1]);
                if(check==0)// need to push new tower i at the end
                {
                    while(cnt>0)
                    {
                        if(check_relative(sorted_tower[i],relative_tower[cnt-1])==2)
                        {
                            break;
                        }
                        cnt--;
                    }
                }
                else if(check==1)
                {
                    continue;
                }
                relative_tower[cnt++]=sorted_tower[i];
            }
        }
//        int cnt=getRelevantTowers();
//        for(int i=0;i<N;i++)
//        {
//            cout<<sorted_tower[i]<<" ";
//        }
//        cout<<endl;
//        for(int i=0;i<cnt;i++)
//        {
//            cout<<p[relative_tower[i]]<<" ";
//        }
//        cout<<endl;
//        cout<<cnt<<endl;
        for(int i=0;i<K;i++)
        {
            int left=0;
            int right=cnt-1;
            int mid=(left+right)/2;
            bool flg=false;
            while(left<=right)
            {
                mid=(left+right)/2;
                int tower=relative_tower[mid];
                if(p[tower]<x[i])
                {
                    left=mid+1;
                }
                else
                {
                    right=mid-1;
                }
            }
//            cout<<"mid "<<relative_tower[mid]<<endl;
//            if(mid==0)// only consider left most tower
//            {
//                if(get_ballon(relative_tower[mid],i)==true)
//                {
//                    flg=true;
//                }
//            }
//            else

            if(get_ballon(relative_tower[mid],i)==true)
            {
                flg=true;
//                  cout<<"here2"<<endl;
            }
                
            else if(mid+1<cnt&&get_ballon(relative_tower[mid+1],i)==true)
            {
                flg=true;
//                   cout<<"here3"<<endl;
            }
            else if(mid>0&&get_ballon(relative_tower[mid-1],i)==true)
            {
                flg=true;
                //                   cout<<"here4"<<endl;
            }


            if(flg==true)
            {
                ans++;
            }
        }
        
        printf("Case #%d: %lld\n",ca,ans);
        
        
    }
    return 0;
}