제출 #697325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697325		abcdehello	Pairs (IOI07_pairs)	C++17	0 / 100	293 ms	9448 KiB

pairs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,b,n,d,m;
void _1d(){
	if (d>m) d=m;
	vector<ll> a(n);
	for (int i=0;i<n;i++) cin >> a[i];
	a.push_back(0);a.push_back(INT_MAX);
	sort(a.begin(),a.end());
	for (int i=1;i<=n;i++){
		ans += (lower_bound(a.begin(),a.end(),a[i]+d+1)-lower_bound(a.begin(),a.end(),a[i]-d))-1;
		cerr << (lower_bound(a.begin(),a.end(),a[i]+d+1)-lower_bound(a.begin(),a.end(),a[i]-d))-1 << endl;
	}
	cout << ans/2 << "\n";
}
void _2d(){
}
void _3d(){
	if (d>3*m) d=3*m;
	vector<ll> a[80][80];
	vector<pair<pair<ll,ll>,ll> > c(0);
	for (int i=0;i<=75;i++){
		for (int j=0;j<=75;j++){
			a[i][j].resize(0);
			a[i][j].push_back(0);
			a[i][j].push_back(INT_MAX);
		}
	}
	for (int i=0;i<n;i++){
		ll x,y,z;
		cin >> x >> y >> z;
		a[x][y].push_back(z);
		c.push_back({{x,y},z});
	}
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++) sort(a[i][j].begin(),a[i][j].end());
	}
	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;
				ll cnt=(lower_bound(a[xx][yy].begin(),a[xx][yy].end(),z+rem+1)-lower_bound(a[xx][yy].begin(),a[xx][yy].end(),z-rem));
				ans += max(cnt-1,0LL);
			}
		}
	}
	cout << ans/2 << "\n";
}
int main(){
	cin >> b >> n >> d >> m;
	if (b==1) _1d();
	else if (b==2) _2d();
	else _3d();
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 6
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10