oj.uz

Submission #595798

# Submission time Handle Problem Language Result Execution time Memory
595798 2022-07-14T07:03:26 Z penguinhacker Pairs (IOI07_pairs) C++17
100 / 100
 245 ms 25268 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, d, m, ft1[200000], ft2[225][225][225];

void solve1() {
	vector<int> a(n);
	for (int& i : a)
		cin >> i;
	sort(a.begin(), a.end());
	ll ans=0;
	for (int i=0, j=0; i<n; ++i) {
		for (; j<n&&a[j]<=a[i]+d; ++j);
		ans+=j-i-1;
	}
	cout << ans << "\n";
}

void upd1(int i, int x) {
	for (++i; i<200000; i+=i&-i)
		ft1[i]+=x;
}

int qry1(int i) {
	int r=0;
	for (++i; i; i-=i&-i)
		r+=ft1[i];
	return r;
}

void upd2(int a, int b, int c, int x) {
	for (int i=a+1; i<225; i+=i&-i)
		for (int j=b+1; j<225; j+=j&-j)
			for (int k=c+1; k<225; k+=k&-k)
				ft2[i][j][k]+=x;
}

int qry2(int a, int b, int c) {
	if (a<0||b<0||c<0)
		return 0;
	int r=0;
	for (int i=a+1; i; i-=i&-i)
		for (int j=b+1; j; j-=j&-j)
			for (int k=c+1; k; k-=k&-k)
				r+=ft2[i][j][k];
	return r;
}

void solve2() {
	vector<ar<int, 2>> points(n);
	for (ar<int, 2>& p : points) {
		int x, y;
		cin >> x >> y, --x, --y;
		p={x+y, x+(m-1-y)};
	}
	sort(points.begin(), points.end());
	ll ans=0;
	for (int i=0, j=0; i<n; ++i) {
		while(points[j][0]+d<points[i][0])
			upd1(points[j++][1], -1);
		ans+=qry1(min(points[i][1]+d, 2*m-2))-qry1(max(points[i][1]-d, 0)-1);
		upd1(points[i][1], 1);
	}
	cout << ans << "\n";
}

void solve3() {
	vector<ar<int, 4>> points(n);
	for (ar<int, 4>& p : points) {
		int x, y, z;
		cin >> x >> y >> z, --x, --y, --z;
		p={x+y+z, x+y+(m-1-z), x+(m-1-y)+z, x+(m-1-y)+(m-1-z)};
	}
	sort(points.begin(), points.end());
	ll ans=0;
	for (int i=0, j=0; i<n; ++i) {
		for (; points[j][0]+d<points[i][0]; ++j)
			upd2(points[j][1], points[j][2], points[j][3], -1);
		int lx=max(points[i][1]-d, 0), rx=min(points[i][1]+d, 3*m-3);
		int ly=max(points[i][2]-d, 0), ry=min(points[i][2]+d, 3*m-3);
		int lz=max(points[i][3]-d, 0), rz=min(points[i][3]+d, 3*m-3);
		ans+=qry2(rx, ry, rz)-qry2(rx, ry, lz-1)-qry2(rx, ly-1, rz)-qry2(lx-1, ry, rz)+qry2(rx, ly-1, lz-1)+qry2(lx-1, ry, lz-1)+qry2(lx-1, ly-1, rz)-qry2(lx-1, ly-1, lz-1);
		upd2(points[i][1], points[i][2], points[i][3], 1);
	}
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int type;
	cin >> type >> n >> d >> m;
	if (type==1)
		solve1();
	else if (type==2)
		solve2();
	else
		solve3();
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 992 KB Output is correct
2 Correct 12 ms 1108 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1492 KB Output is correct
2 Correct 17 ms 1492 KB Output is correct
3 Correct 17 ms 1484 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1624 KB Output is correct
2 Correct 26 ms 1700 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1900 KB Output is correct
2 Correct 34 ms 1880 KB Output is correct
3 Correct 30 ms 1876 KB Output is correct
4 Correct 40 ms 1872 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2764 KB Output is correct
2 Correct 31 ms 2772 KB Output is correct
3 Correct 32 ms 2772 KB Output is correct
4 Correct 42 ms 2736 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11860 KB Output is correct
2 Correct 6 ms 11860 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3544 KB Output is correct
2 Correct 87 ms 3420 KB Output is correct
3 Correct 71 ms 3480 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 17972 KB Output is correct
2 Correct 164 ms 17952 KB Output is correct
3 Correct 67 ms 17956 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 25268 KB Output is correct
2 Correct 193 ms 25212 KB Output is correct
3 Correct 105 ms 25164 KB Output is correct