Submission #371050

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
371050	2021-02-25T16:49:21 Z	cheissmart	Pairs (IOI07_pairs)	C++14	100 / 100	414 ms	52944 KB

pairs

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int n, d, m;

struct solve1 {
	solve1() {
		vi a(n);
		for(int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(ALL(a));
		ll ans = 0;
		for(int i = 0, j = 0; i < n; i++) {
			while(a[i] - a[j] > d) j++;
			assert(a[i] - a[j] <= d);
			ans += i - j;
		}
		cout << ans << '\n';
	}
};


struct solve2 {
	static const int N = 150000 + 7;
	int bit[N];
	void add(int y, int val) {
		for(; y < N; y += y & -y)
			bit[y] += val;
	}
	int qry(int y) {
		int res = 0;
		for(; y; y -= y & -y)
			res += bit[y];
		return res;
	}
	solve2() {
		memset(bit, 0, sizeof bit);
		V<pi> a(n);
		for(int i = 0; i < n; i++) {
			int x, y;
			cin >> x >> y;
			a[i] = {x - y, x + y};
		}
		V<array<int, 3>> ev;
		ll ans = 0;
		for(int i = 0; i < n; i++) {
			ev.PB({a[i].F, 0, a[i].S});
			ev.PB({a[i].F + d, 1, a[i].S});
		}
		sort(ALL(ev));
		deque<pi> dk;
		for(auto e:ev) {
			if(e[1] == 0) { // add point
				add(e[2], 1);
				dk.EB(e[0], e[2]);
			} else { // qry
				while(dk.size() && dk[0].F < e[0] - 2 * d) {
					add(dk[0].S, -1);
					dk.pop_front();
				}
				int l = max(e[2] - d, 1), r = min(e[2] + d, N - 1);
				ans += qry(r) - qry(l - 1) - 1;
			}
		}
		cout << ans / 2 << '\n';
	}
};

struct solve3 {
	static const int N = 75 * 3;

#define ADD(i, x) for(int i = x; i < N; i += i & -i)
#define QRY(i, x) for(int i = x; i; i -= i & -i)

	int bit[N][N][N];
	void add(int x, int y, int z, int val) {
		ADD(i, x) ADD(j, y) ADD(k, z) {
			bit[i][j][k] += val;
		}
	}
	int qry(int x, int y, int z) {
		int res = 0;
		QRY(i, x) QRY(j, y) QRY(k, z) res += bit[i][j][k];
		return res;
	}
	solve3() {
		memset(bit, 0, sizeof bit);
		V<array<int, 4>> a(n);
		for(int i = 0; i < n; i++) {
			int x, y, z;
			cin >> x >> y >> z;
			int f1 = x + y + z - 2; // [1, 75 * 3 - 2]
			int f2 = x + y - z + 75 - 1; // [1, 75 * 3 - 2]
			int f3 = x - y + z + 75 - 1; // [1, 75 * 3 - 2]
			int f4 = x - y - z + m * 2; // [1, 75 * 3 - 2]
			a[i] = {f1, f2, f3, f4};
		}
		V<array<int, 5>> ev;
		ll ans = 0;
		for(int i = 0; i < n; i++) {
			ev.PB({a[i][0], 0, a[i][1], a[i][2], a[i][3]});
			ev.PB({a[i][0] + d, 1, a[i][1], a[i][2], a[i][3]});
		}
		sort(ALL(ev));
		deque<array<int, 4>> dk;
		for(auto e:ev) {
			if(e[1] == 0) { // add point
				add(e[2], e[3], e[4], 1);
				dk.PB({e[0], e[2], e[3], e[4]});
			} else { // qry
				while(dk.size() && dk[0][0] < e[0] - 2 * d) {
					add(dk[0][1], dk[0][2], dk[0][3], -1);
					dk.pop_front();
				}
				int l1 = max(e[2] - d, 1), r1 = min(e[2] + d, N - 1);
				int l2 = max(e[3] - d, 1), r2 = min(e[3] + d, N - 1);
				int l3 = max(e[4] - d, 1), r3 = min(e[4] + d, N - 1);
				ans += qry(r1, r2, r3);
				ans -= qry(l1-1, r2, r3);
				ans -= qry(r1, l2-1, r3);
				ans -= qry(r1, r2, l3-1);
				ans += qry(l1-1, l2-1, r3);
				ans += qry(r1, l2-1, l3-1);
				ans += qry(l1-1, r2, l3-1);
				ans -= qry(l1-1, l2-1, l3-1);
				ans--;
			}
		}
		cout << ans / 2 << '\n';
	}
};

signed main()
{
	IO_OP;

	int b;
	cin >> b >> n >> d >> m;
	if(b == 1) new solve1();
	else if(b == 2) new solve2();
	else new solve3();


}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	1004 KB	Output is correct
2	Correct	14 ms	1004 KB	Output is correct

Subtask #4
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1004 KB	Output is correct
2	Correct	19 ms	1004 KB	Output is correct

Subtask #5
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1004 KB	Output is correct
2	Correct	20 ms	1004 KB	Output is correct
3	Correct	20 ms	1004 KB	Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	5216 KB	Output is correct
2	Correct	55 ms	5216 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	5344 KB	Output is correct
2	Correct	65 ms	5216 KB	Output is correct
3	Correct	67 ms	5216 KB	Output is correct
4	Correct	58 ms	5216 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	5216 KB	Output is correct
2	Correct	58 ms	5216 KB	Output is correct
3	Correct	61 ms	5212 KB	Output is correct
4	Correct	61 ms	5216 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	45164 KB	Output is correct
2	Correct	26 ms	45036 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	52060 KB	Output is correct
2	Correct	166 ms	52688 KB	Output is correct
3	Correct	142 ms	52688 KB	Output is correct

Subtask #12
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	273 ms	52060 KB	Output is correct
2	Correct	341 ms	52944 KB	Output is correct
3	Correct	127 ms	52908 KB	Output is correct

Subtask #13
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	414 ms	52060 KB	Output is correct
2	Correct	357 ms	52816 KB	Output is correct
3	Correct	136 ms	52944 KB	Output is correct

Submission #371050

Compilation message