Codeforces #548 Div2 F. Dish Shopping

なんか面倒なだけで面白さはあまり感じない問題…。
https://codeforces.com/contest/1139/problem/F

問題

M枚の皿があり、それぞれパラメータとして価格P[i]、基準値S[i]、美しさB[i]がある。
さて、ここで人が来て皿を買うことを考える。
この人の収入をInc[j]とし、好みの美しさをPref[j]とする。

この人は、P[i]≦Inc[j]≦S[i]でありかつ|B[i]-Pref[j]|≦(Inc[j]-P[i])を満たす皿を買う。
人の情報がN人分与えられるとき、それぞれに対し購入可能な皿の枚数を求めよ。

解法

P[i]、Inc[j]、S[i]に順序性があるので、この順に走査していくことを考える。
あとは|B[i]-Pref[j]|≦(Inc[j]-P[i])をどう判定するかである。

B[i]-Pref[j]

≦(Inc[j]-P[i])が成り立つには(B[i]-Pref[j])≦(Inc[j]-P[i])かつ(Pref[j]-B[i])≦(Inc[j]-P[i])ならよい。

また平面走査の関係上P[i]≦Inc[j]が必ず成り立つ皿のみを対象とするので、右辺は正である。
左辺は必ず片方は0以下なので式を満たす。

上記式を移行すると、

• P[i]+B[i]≦Inc[j]+Pref[j]
• P[i]-B[i]≦Inc[j]-Pref[j]

の両者を満たすiを数え上げればよいので、P[i]+B[i]およびP[i]-B[i]それぞれ座標圧縮したうえでBITで個数を数え上げよう。

int N,M;
ll P[101010],S[101010],B[101010],inc[101010],pref[101010];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> btp,btm;
vector<pair<int,int>> ev;

int ret[101010];
int num;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<ll> CP,CM;
	CP.push_back(-1LL<<40);
	CM.push_back(-1LL<<40);
	
	FOR(i,N) {
		cin>>P[i];
		ev.push_back({P[i],i});
	}
	FOR(i,N) {
		cin>>S[i];
		ev.push_back({S[i],200000+i});
	}
	FOR(i,N) {
		cin>>B[i];
		CP.push_back(B[i]+P[i]);
		CM.push_back(P[i]-B[i]);
	}
	FOR(i,M) {
		cin>>inc[i];
		ev.push_back({inc[i],100000+i});
	}
	FOR(i,M) {
		cin>>pref[i];
		CP.push_back(inc[i]+pref[i]);
		CM.push_back(inc[i]-pref[i]);
	}
	sort(ALL(CP));
	sort(ALL(CM));
	CP.erase(unique(ALL(CP)),CP.end());
	CM.erase(unique(ALL(CM)),CM.end());
	sort(ALL(ev));
	FORR(e,ev) {
		x=e.second;
		if(x<100000) {
			num++;
			y=lower_bound(ALL(CP),B[x]+P[x])-CP.begin();
			btp.add(y,1);
			y=lower_bound(ALL(CM),P[x]-B[x])-CM.begin();
			btm.add(y,1);
		}
		else if(x<200000) {
			x-=100000;
			y=lower_bound(ALL(CP),inc[x]+pref[x])-CP.begin();
			ret[x]+=btp(y);
			y=lower_bound(ALL(CM),inc[x]-pref[x])-CM.begin();
			ret[x]+=btm(y);
			ret[x]-=num;
		}
		else {
			x-=200000;
			num--;
			y=lower_bound(ALL(CP),B[x]+P[x])-CP.begin();
			btp.add(y,-1);
			y=lower_bound(ALL(CM),P[x]-B[x])-CM.begin();
			btm.add(y,-1);
		}
	}
	FOR(i,M) cout<<ret[i]<<" ";
	cout<<endl;
	
}

まとめ

うーん。まぁ思いつけて良かったけど。