Submission #438844

#	Time	Username	Problem	Language	Result	Execution time	Memory
438844		sinamhdv	Pairs (IOI07_pairs)	C++11	100 / 100	681 ms	304328 KiB

pairs

// IOI07_pairs
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define MAXA 75100

#define M3 240
const int bs = 80;

int B, n, d, m;
ll ans;
pii pnt[MAXN];
vector<int> seg[4 * MAXN];
int ps[80][M3][M3];

void build(int v = 1, int l = 0, int r = n - 1)
{
	if (l == r)
	{
		seg[v].pb(pnt[l].sc);
		return;
	}
	int mid = (r + l) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	merge(all(seg[2 * v]), all(seg[2 * v + 1]), back_inserter(seg[v]));
}

int get(int L, int R, int ly, int ry, int v = 1, int l = 0, int r = n - 1)
{
	if (l > R || r < L) return 0;
	if (l >= L && r <= R)
		return upper_bound(all(seg[v]), ry) - lower_bound(all(seg[v]), ly);
	int mid = (r + l) / 2;
	return get(L, R, ly, ry, 2 * v, l, mid) + get(L, R, ly, ry, 2 * v + 1, mid + 1, r);
}

int32_t main(void)
{
	fast_io;
	cin >> B >> n >> d >> m;
	if (B == 1)
	{
		vector<int> vec(m + 10);
		int x[MAXN] = {};
		FOR(i, 0, n)
		{
			cin >> x[i];
			vec[x[i]]++;
		}
		FOR(i, 1, (int)vec.size()) vec[i] += vec[i - 1];
		FOR(i, 0, n) ans += vec[min(x[i] + d, m+3)] - vec[max(x[i] - d - 1, 0)];
		ans -= n;
		ans /= 2;
		cout << ans << endl;
		return 0;
	}
	else if (B == 3)
	{
		int x[MAXN], y[MAXN], z[MAXN];
		FOR(i, 0, n)
		{
			int a, b, c;
			cin >> a >> b >> c;
			x[i] = a;
			y[i] = b + c;
			z[i] = b - c;
			ps[x[i]][y[i]+bs][z[i]+bs]++;
		}

		FOR(i, 0, 80)
		{
			FOR(j, 1, M3) FOR(k, 1, M3) ps[i][j][k] += ps[i][j - 1][k] + ps[i][j][k - 1] - ps[i][j - 1][k - 1];
		}
		
		FOR(i, 0, n)
		{
			int up = max(x[i] - d, 0);
			int dn = min(x[i] + d, m);
			FOR(l, up, dn + 1)
			{
				int dis = abs(x[i] - l);
				d -= dis;
				int y1 = max(-77, y[i] - d) - 1 + bs;
				int y2 = min(155, y[i] + d) + bs;
				int z1 = max(-77, z[i] - d) - 1 + bs;
				int z2 = min(155, z[i] + d) + bs;
				ans += ps[l][y2][z2] - ps[l][y1][z2] - ps[l][y2][z1] + ps[l][y1][z1];
				d += dis;
			}
		}

		ans -= n;
		ans /= 2;
		cout << ans << endl;
		return 0;
	}

	// B == 2
	FOR(i, 0, n)
	{
		int x, y;
		cin >> x >> y;
		pnt[i].fr = x + y;
		pnt[i].sc = x - y;
	}
	sort(pnt, pnt + n);
	build();

	FOR(i, 0, n)
	{
		int lx = pnt[i].fr - d;
		int rx = pnt[i].fr + d;
		int ly = pnt[i].sc - d;
		int ry = pnt[i].sc + d;
		int L = lower_bound(pnt, pnt + n, mp(lx, -INF)) - pnt;
		int R = lower_bound(pnt, pnt + n, mp(rx + 1, -INF)) - pnt - 1;
		ans += get(L, R, ly, ry);
	}

	ans -= n;
	ans /= 2;
	cout << ans << endl;

	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10