PCK2014予選 「天体観測」
AOJに問題が登録されたので解いてみました。
AOJ0302
予め星の輝きをソートしておきます。
ある星Aを決めると、(Aの輝き)以上かつ(Aの輝き+d)に最も近い星までが星座を作る星になるので、
その様に選んだ時の長方形の面積Sの大きさは
S = (星座内で最も大きいX座標-最も小さいX座標)(最も大きいY座標-最も小さいY座標)
となり、これを高速に求めるためにRMQを用います。
全ての星に対してこの操作を行った時の最も大きい長方形の面積が解となります。
#include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(I,N) for(int I = 0;I<(int)(N);I++) #define P pair<ll,ll> #define pb push_back #define INF 10000000000 vector<P> datas; P sorted[200001]; ll sortedV[200001]; ll BSEG[1<<19][2];///x,y ll MSEG[1<<19][2];///x,y void updataB(int index,int t){ if(index==0)return; int l = index*2,r = index*2+1; ll tmp = BSEG[index][t]; if(BSEG[l][t]<BSEG[r][t]){ BSEG[index][t] = BSEG[r][t]; }else{ BSEG[index][t] = BSEG[l][t]; } if(BSEG[index][t]==tmp)return; updataB(index/2,t); } void updataM(int index,int t){ if(index==0)return; int l = index*2,r = index*2+1; ll tmp = MSEG[index][t]; if(MSEG[l][t]>MSEG[r][t]){ MSEG[index][t] = MSEG[r][t]; }else{ MSEG[index][t] = MSEG[l][t]; } if(MSEG[index][t]==tmp)return; updataM(index/2,t); } ll getMin(int a,int b,int k,int l,int r,int t){ if(b<l||r<a)return INF; if(a<=l&&r<=b)return MSEG[k][t]; ll lm = getMin(a,b,k*2,l,(r-l)/2+l,t); ll rm = getMin(a,b,k*2+1,(r-l)/2+l+1,r,t); return min(lm,rm); } ll getMax(int a,int b,int k,int l,int r,int t){ if(b<l||r<a)return 0; if(a<=l&&r<=b)return BSEG[k][t]; ll lm = getMax(a,b,k*2,l,(r-l)/2+l,t); ll rm = getMax(a,b,k*2+1,(r-l)/2+l+1,r,t); return max(lm,rm); } int main(){ int i,j; ll n,d,x,y,c; cin>>n>>d; FOR(i,n){ cin>>x>>y>>c; P data = P(x,y); datas.pb(data); sorted[i] = P(c,datas.size()-1); sortedV[i] = c; } sort(sorted,sorted+n); sort(sortedV,sortedV+n); int index = 1; while(index<n)index*=2; fill_n(*BSEG,(1<<19)*2,0); fill_n(*MSEG,(1<<19)*2,INF); FOR(i,n){ P data = datas[sorted[i].second]; x = data.first; y = data.second; BSEG[index+i][0] = x; MSEG[index+i][0] = x; BSEG[index+i][1] = y; MSEG[index+i][1] = y; updataB((index+i)/2,0); updataB((index+i)/2,1); updataM((index+i)/2,0); updataM((index+i)/2,1); } ll ans = 0; FOR(i,n){ ll source = sorted[i].first; ll r = source+d; int li = i; int ri = upper_bound(sortedV,sortedV+n,r)-sortedV-1; if(li==ri)continue; ll sum = (getMax(li,ri,1,0,index-1,0)-getMin(li,ri,1,0,index-1,0)) *(getMax(li,ri,1,0,index-1,1)-getMin(li,ri,1,0,index-1,1)); ans = max(ans,sum); } cout<<ans<<endl; return 0; }