Submission #5224012

---

Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, x[50009], y[50009];
vector<int> cx[50309], cy[50309];
int solve(int r)
{
	int ret = 0;
	for (int i = 0; i < n; i++)
    {
		for (int j = 1; j <= 220; j++)
        {
			int ptl = lower_bound(cx[x[i] + j].begin(), cx[x[i] + j].end(), y[i] + 1) - cx[x[i] + j].begin();
			int ptr = lower_bound(cx[x[i] + j].begin(), cx[x[i] + j].end(), y[i] + r / j + 1) - cx[x[i] + j].begin();
			ret += ptr - ptl;
		}
		for (int j = 1; j * 221 <= r; j++)
        {
			int ptl = lower_bound(cy[y[i] + j].begin(), cy[y[i] + j].end(), x[i] + 221) - cy[y[i] + j].begin();
			int ptr = lower_bound(cy[y[i] + j].begin(), cy[y[i] + j].end(), x[i] + max(r / j, 220) + 1) - cy[y[i] + j].begin();
			ret += ptr - ptl;
		}
	}
	return ret;
}
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int s1, s2;
	cin >> n >> s1 >> s2;
	for (int i = 0; i < n; i++)
    {
		cin >> x[i] >> y[i]; x[i]--, y[i]--;
		cx[x[i]].push_back(y[i]);
		cy[y[i]].push_back(x[i]);
	}
	for (int i = 0; i < 50000; i++)
    {
		sort(cx[i].begin(), cx[i].end());
		sort(cy[i].begin(), cy[i].end());
	}
	cout << solve(s2) - solve(s1 - 1) << endl;
	return 0;
}

Submission Info

Judge Result