oj.uz

Submission #899643

# Submission time Handle Problem Language Result Execution time Memory
899643 2024-01-06T17:30:45 Z Nonoze Pairs (IOI07_pairs) C++17
64 / 100
 4000 ms 524288 KB 
#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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1112 KB Output is correct
2 Correct 11 ms 1116 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1116 KB Output is correct
2 Correct 14 ms 1116 KB Output is correct
3 Correct 13 ms 1112 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1880 KB Output is correct
2 Correct 553 ms 2668 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 9892 KB Output is correct
2 Execution timed out 4066 ms 10072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 255 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2812 KB Output is correct
2 Correct 80 ms 3428 KB Output is correct
3 Correct 95 ms 3280 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 4700 KB Output is correct
2 Execution timed out 4016 ms 5484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1917 ms 6508 KB Output is correct
2 Execution timed out 4029 ms 6488 KB Time limit exceeded
3 Halted 0 ms 0 KB -