oj.uz

Submission #438844

# Submission time Handle Problem Language Result Execution time Memory
438844 2021-06-28T17:44:16 Z sinamhdv Pairs (IOI07_pairs) C++11
100 / 100
 681 ms 304328 KB 
// 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10828 KB Output is correct
2 Correct 7 ms 10828 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 304328 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11168 KB Output is correct
2 Correct 18 ms 11084 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 285000 KB Output is correct
2 Correct 362 ms 285080 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 285076 KB Output is correct
2 Correct 333 ms 285124 KB Output is correct
3 Correct 340 ms 285016 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10904 KB Output is correct
2 Correct 9 ms 10956 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 25200 KB Output is correct
2 Correct 93 ms 25368 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 25156 KB Output is correct
2 Correct 221 ms 25304 KB Output is correct
3 Correct 190 ms 25280 KB Output is correct
4 Correct 243 ms 25316 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 25236 KB Output is correct
2 Correct 243 ms 25280 KB Output is correct
3 Correct 187 ms 25368 KB Output is correct
4 Correct 176 ms 25388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28824 KB Output is correct
2 Correct 34 ms 28868 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 29144 KB Output is correct
2 Correct 66 ms 29256 KB Output is correct
3 Correct 64 ms 29080 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 29120 KB Output is correct
2 Correct 485 ms 29056 KB Output is correct
3 Correct 185 ms 29764 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 29088 KB Output is correct
2 Correct 681 ms 29764 KB Output is correct
3 Correct 294 ms 29764 KB Output is correct