合宿 Starry Sky
O(N^2)アルゴリズムはやっぱり見つけられませんでした。ごめんなさい・・・
ですが、なんとかATCODER上では通しました。
枝刈りは、
- それぞれの星で写真を取れる最大の長さで、長さを固定してやるのですが、そのとき、その長さをとる星は必ず取らなければならない(そうでないなら他の長さでやれって話ですよね)ので、その星のまわりについてのみイベントを作ってadd・queryするだけでよいです
これだけで、普通にせぐ木使っても通ります
ちなみに、僕が何故O(N^2)と勘違いしたかというと、
星iの写真を取るときの最大の長さで写真の大きさを固定するとすると、
さっきの枝刈りより、写りうる星の座標のX座標は Xi-Li<=x<=Xi+Li
Y座標は、 Yi-Li<=y<=Yi+Li
写真を取るときの場所を左下の点で決めるとし、
ある写真に写りうる星をjとおくと、
セグ木にaddするのは、Xj-Liで[Yj-Li,Yj]の範囲です
また、減らすのは、Xiで[Yj-Li,Yj]の範囲です。・・・(1)
ここで、自分は(1)をXi+Liで[Yj-Li,Yj]の範囲と間違えてしてしまっていたため、
星iを必ず写真に載せるという条件から、
減らすクエリーは必ずX座標はXiより大きくなるので、
あっこれ減らすクエリーなしだし累積和でいけんじゃんw ktkr!!!!!とかおもってました
本当にごめんなさい・・・
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #define REP(i,m) for(int i=0;i<(int)m;++i) #define REPN(i,m,in) for(int i=in;i<(int)m;++i) #define pb push_back #define mp make_pair #define fr first #define ALL(t) (t).begin(),(t).end() #define sc second #define dump(x) cerr << #x << " = " << (x) << endl; #define prl cerr<<"called:"<< __LINE__<<endl; using namespace std; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef long double ld; typedef pair<int,int> pi; const int INF=1e9+5; int val[16000],all[16000]; int l[16000],r[16000]; struct segtree{ int n; void init(int n_){ n=1; while(n<n_) n<<=1; REP(i,n*2) val[i]=0,all[i]=0; REP(i,n_){ l[i+n-1]=i; r[i+n-1]=i+1; } REPN(i,n,n_) l[i+n-1]=r[i+n-1]=n_; for(int i=n-2;i>=0;--i){ l[i]=l[i*2+1]; r[i]=r[i*2+2]; } } int a,b,v; void add(int node){ if(a<=l[node] && r[node]<=b){ all[node]+=v; val[node]+=v; return; } if(b<=l[node] || r[node]<=a) return; add(node*2+1); add(node*2+2); val[node]=max(val[node*2+1],val[node*2+2])+all[node]; } inline void ad(int a_,int b_,int v_){ a=a_;b=b_;v=v_; add(0); } inline int q(){ return val[0]; } }; struct star{ int x,y,l; star(int sx,int sy,int sl){ x=sx;y=sy;l=sl; } star(){} }; segtree seg; star s[4005]; int n; int ykind[4005]; pi event1[4005],event2[4005]; int cnt,cnt2; bool cmp_x(const star& a,const star& b){ return a.x<b.x; } #define FIND(a,n,k) (lower_bound(a,a+n,k)-a) #define FIND2(a,n,k) (upper_bound(a,a+n,k)-a) int main(){ scanf("%d",&n); REP(i,n){ int x,y,l;scanf("%d%d%d",&x,&y,&l); ykind[i]=y; s[i]=star(x,y,l); } sort(ykind,ykind+n); sort(s,s+n,cmp_x); int res=0; REP(i,n){ int len=s[i].l; int left=s[i].x-len,bottom=s[i].y-len, right=s[i].x+len,top=s[i].y+len; cnt=0; seg.init(n); REP(j,n){ if(s[j].x>=left && s[j].x<=right && s[j].y>=bottom && s[j].y<=top && s[j].l>=len){ event1[cnt]=mp(s[j].x-len,s[j].y-len); event2[cnt++]=mp(s[j].x,s[j].y-len); } } int j=0,k=0; event1[cnt]=mp(INF,INF); event2[cnt]=mp(INF,INF); while(j<cnt || k<cnt){ if(event1[j].fr<=event2[k].fr){ if(event1[j].fr>s[i].x) break; seg.ad(FIND(ykind,n,event1[j].sc), FIND2(ykind,n,min(event1[j].sc+len,s[i].y)),1); res=max(res,seg.q()); ++j; }else{ if(event2[k].fr>=s[i].x) break; seg.ad(FIND(ykind,n,event2[k].sc), FIND2(ykind,n,min(event2[k].sc+len,s[i].y)),-1); ++k; } } } printf("%d\n",res); return 0; }