Submission #595798

#	Time	Username	Problem	Language	Result	Execution time	Memory
595798		penguinhacker	Pairs (IOI07_pairs)	C++17	100 / 100	245 ms	25268 KiB

pairs

#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 / 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