oj.uz

Submission #697332

# Submission time Handle Problem Language Result Execution time Memory
697332 2023-02-09T09:28:18 Z abcdehello Pairs (IOI07_pairs) C++17
70 / 100
 2451 ms 8256 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,b,n,d,m;
void _1d(){
	vector<ll> a(n);
	for (int i=0;i<n;i++) cin >> a[i];
	a.push_back(INT_MAX);
	sort(a.begin(),a.end());
	int l=0,r=0;
	for (int i=0;i<n;i++){
		while (a[l]+d<a[i]) l++;
		while (r<n&&a[r+1]<=a[i]+d) r++;
		//cerr << l << " " << r << endl;
		ans+=r-l;
	}
	cout << ans/2 << "\n";
}
void _2d(){
}
void _3d(){
	ll a[80][80][80];
	for (int i=0;i<=m;i++){
		for (int j=0;j<=m;j++){
			for (int k=0;k<=m;k++) a[i][j][k]=0;
		}
	}
	vector<pair<pair<ll,ll>,ll> > c(0);
	for (int i=0;i<n;i++){
		ll x,y,z;
		cin >> x >> y >> z;
		a[x][y][z]++;
		c.push_back({{x,y},z});
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=m;j++){
			for (int k=1;k<=m;k++) a[i][j][k]+=a[i][j][k-1];
		}
	}
	for (int i=0;i<n;i++){
		ll x=c[i].first.first,y=c[i].first.second,z=c[i].second;
		for (int xx=0;xx<=m;xx++){
			for (int yy=0;yy<=m;yy++){
				ll rem=d-abs(x-xx)-abs(y-yy);
				if (rem<0) continue;
				ans+=a[xx][yy][min(m,z+rem)]-a[xx][yy][max(0LL,z-rem-1)];
				if (x==xx&&y==yy) ans--;
			}
		}
	}
	cout << ans/2 << "\n";
}
int main(){
	cin >> b >> n >> d >> m;
	if (b==1) _1d();
	else if (b==2) _2d();
	else _3d();
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1856 KB Output is correct
2 Correct 24 ms 2244 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1740 KB Output is correct
2 Correct 44 ms 2720 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1852 KB Output is correct
2 Correct 40 ms 2612 KB Output is correct
3 Correct 41 ms 2740 KB Output is correct

Subtask #6
0 / 7.0

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

Subtask #7
0 / 7.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4348 KB Output is correct
2 Correct 34 ms 4336 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7496 KB Output is correct
2 Correct 104 ms 8032 KB Output is correct
3 Correct 94 ms 8028 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 7488 KB Output is correct
2 Correct 1566 ms 8228 KB Output is correct
3 Correct 1741 ms 8256 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 7456 KB Output is correct
2 Correct 2297 ms 8256 KB Output is correct
3 Correct 2451 ms 8228 KB Output is correct