Codeforces #1117 : Div2. D. Bermuda Rectangle

そこそこの出来。
https://codeforces.com/contest/2257/problem/D

問題

正整数Sとクエリとして座標(x,y)が指定される。
以下の問いに答えよ。

座標(s,t)のうち、s*t=Sとなる正整数s,tの対複数に対し、(0,0)-(s,t)が両端点を成す軸に平行な長方形の和集合を考える。
この和集合と、(0,0)-(x,y)が両端点を成す軸に平行な長方形の共通部分の面積を求めよ。

解法

あらかじめ(s,t)の組を列挙し、sを昇順に並べた配列と、sごとに(0,0)-(s,∞)との共通部分の面積を求めておく。
tについても同様に昇順に並べた配列を作っておく。

(x,y)に対し、先の配列を二分探索することで、(0,0)-(x,∞)と、和集合の共通部分の面積を求めることができる。
次に、Y座標がy以上になる最大のX座標x'をやはり二分探索で求め、(0,y)-(x',∞)の面積を引こう。

int T;
ll S;
int Q;

ll X[202020],Y[202020];
ll SA[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S>>Q;
		vector<pair<ll,ll>> V;
		for(ll a=1;a*a<=S;a++) if(S%a==0) {
			V.push_back({a,S/a});
			if(a*a!=S) V.push_back({S/a,a});
		}
		V.push_back({0,1LL<<60});
		V.push_back({S+2,0});
		sort(ALL(V));
		int N=V.size()-1;
		FOR(i,N) {
			X[i]=V[i].first;
			Y[N-1-i]=V[i].second;
			if(i) {
				SA[i]=SA[i-1]+V[i].second*(V[i].first-V[i-1].first);
			}
		}
		while(Q--) {
			ll x,y;
			cin>>x>>y;
			
			int tx=lower_bound(X,X+N,x)-X;
			if(V[tx].second>=y) {
				cout<<x*y<<endl;
				continue;
			}
			tx--;
			ll ret=0;
			ret=SA[tx]+(x-X[tx])*V[tx+1].second;
			
			int ty=lower_bound(Y,Y+N,y)-Y;
			ty=N-1-ty;
			ret-=SA[ty]-V[ty].first*y;
			cout<<ret<<endl;
			
		}
		
		
	}
}

まとめ

解法は色々ありそうだけど、簡潔に書くのはちょっと悩む。