Submission #697332

#	Time	Username	Problem	Language	Result	Execution time	Memory
697332		abcdehello	Pairs (IOI07_pairs)	C++17	70 / 100	2451 ms	8256 KiB

pairs

#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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10