Submission #899643

#	Time	Username	Problem	Language	Result	Execution time	Memory
899643		Nonoze	Pairs (IOI07_pairs)	C++17	64 / 100	4066 ms	524288 KiB

pairs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define sz(x) (int)(x.size())

using namespace std;
using namespace __gnu_pbds;

typedef
tree<
  int,
  null_type,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;

struct grid3d {
	int x, y, z;
};

struct grid2d {
	int x, y;
};

int b, n, d, m;

void subtask1() {
	vector<int> cos(n);
	for (auto &u: cos) cin >> u;
	sort(cos.begin(), cos.end());
	int pro=1;
	int ans=0;
	for (int i=0; i<n; i++) {
		pro=max(pro, i+1);
		while (pro<n && cos[pro]-cos[i]<=d) pro++;
		pro--;
		ans+=pro-i;
	}
	cout << ans << endl;
}


void subtask2() {
	vector<grid2d> cos(n);
	for (auto &u: cos) cin >> u.x >> u.y, m=max(m, max(u.x, u.y));
	if (n<=10000) {
		int ans=0;
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {
				if (abs(cos[i].x-cos[j].x)+abs(cos[i].y-cos[j].y)<=d) ans++;
			}
		}
		cout << ans << endl;
	} else {
		int ans=0;
		vector<vector<int>> tab(m+1, vector<int>(m+1, 0));
		for (auto u: cos) tab[u.x][u.y]++;
		for (int i=0; i<n; i++) {
			int x=cos[i].x, y=cos[i].y;
			for (int a=max(0LL, x-d); a<=min(m, x+d); a++) {
				int restant=d-abs(x-a);
				for (int b=max(0LL, y-restant); b<=min(m, y+restant); b++) {
					ans+=tab[a][b];
				}
			}
			ans--;
		}
		cout << ans/2 << endl;
	}
}
void subtask3() {
	vector<grid3d> cos(n);
	for (auto &u: cos) {
		cin >> u.x >> u.y >> u.z;
		m=max(m, max(u.x, max(u.y, u.z)));
	}
	if (n<=10000) {
		int ans=0;
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {
				if (abs(cos[i].x-cos[j].x)
					+abs(cos[i].y-cos[j].y)
					+abs(cos[i].z-cos[j].z)<=d) ans++;
			}
		}
		cout << ans << endl;
	} else {
		int ans=0;
		int comp=0;
		vector<vector<vector<int>>> tab(m+1, vector<vector<int>>(m+1, vector<int>(m+1, 0)));
		for (int i=0; i<n; i++) tab[cos[i].x][cos[i].y][cos[i].z]++;
		for (int i=0; i<n; i++) {
			int x=cos[i].x, y=cos[i].y, z=cos[i].z;
			for (int a=max(0LL, x-d); a<=min(m, x+d); a++) {
				int restant=d-abs(x-a);
				for (int b=max(0LL, y-restant); b<=min(m, y+restant); b++) {
					int res=restant-abs(y-b);
					for (int c=max(0LL, z-res); c<=min(m, z+res); c++) {
						if (tab[a][b][c]>1) comp++;
						ans+=tab[a][b][c];
					}
				}
			}
			ans--;
		}
		cout << ans/2 << endl;
	}
}


void solve() {
	cin >> b >> n >> d >> m;
	m=0;
	if (b==1) subtask1();
	if (b==2) subtask2();
	if (b==3) subtask3();
	return;
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	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: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10