oj.uz

Submission #438838

# Submission time Handle Problem Language Result Execution time Memory
438838 2021-06-28T17:29:31 Z sinamhdv Pairs (IOI07_pairs) C++11
70 / 100
 434 ms 304320 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
const int bs = 80;

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

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, 220) FOR(k, 1, 220) 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);
			dbg(i);
			dbg(up);
			dbg(dn);
			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)
//		cout << "( " << pnt[i].fr << ", " << pnt[i].sc << ") ";
//	cout << endl;

	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 8 ms 10828 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 304320 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10904 KB Output is correct
2 Correct 17 ms 10892 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 284840 KB Output is correct
2 Correct 353 ms 284852 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 284748 KB Output is correct
2 Correct 336 ms 284940 KB Output is correct
3 Correct 328 ms 284852 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10956 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 143 ms 24896 KB Output is correct
2 Correct 95 ms 25548 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 25052 KB Output is correct
2 Correct 215 ms 25756 KB Output is correct
3 Correct 194 ms 25656 KB Output is correct
4 Correct 205 ms 25720 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 24972 KB Output is correct
2 Correct 259 ms 26048 KB Output is correct
3 Correct 182 ms 26128 KB Output is correct
4 Correct 171 ms 26048 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 25932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 25924 KB Output is correct
2 Correct 59 ms 25928 KB Output is correct
3 Correct 60 ms 25940 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 25944 KB Output is correct
2 Incorrect 434 ms 26148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 365 ms 26052 KB Output isn't correct
2 Halted 0 ms 0 KB -