oj.uz

Submission #899642

# Submission time Handle Problem Language Result Execution time Memory
899642 2024-01-06T16:38:31 Z Nonoze Pairs (IOI07_pairs) C++17
47 / 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;
	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<bool>> tab(m+1, vector<bool>(m+1, false));
		for (auto u: cos) tab[u.x][u.y]=true;
		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++) {
					if (tab[a][b]) ans++;
				}
			}
		}
		cout << (ans-n)/2 << endl;
	}
}

void subtask3() {
	vector<grid3d> cos(n);
	for (auto &u: cos) cin >> u.x >> 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;
		vector<vector<vector<bool>>> tab(m+1, vector<vector<bool>>(m+1, vector<bool>(m+1, false)));
		for (auto u: cos) tab[u.x][u.y][u.z]=true;
		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]) ans++;
					}

				}
			}
		}
		cout << (ans-n)/2 << endl;
	}
}


void solve() {
	cin >> b >> n >> d >> m;
	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 1 ms 348 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 1116 KB Output is correct
2 Correct 10 ms 1116 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1116 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 1112 KB Output is correct
2 Correct 14 ms 1496 KB Output is correct
3 Correct 16 ms 1116 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 2192 KB Output is correct
2 Execution timed out 4030 ms 2904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 271 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 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 3060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2509 ms 3208 KB Output is correct
2 Execution timed out 4045 ms 3932 KB Time limit exceeded
3 Halted 0 ms 0 KB -