#include<bits/stdc++.h>
using namespace std;
int tip, n, d, m;
long long ans;
struct tp
{
int x, y, z;
};
tp vv[10002];
void solvesmall()
{
for(int i = 1; i <= n; ++i)
{
cin >> vv[i].x;
if(tip >= 2)
cin >> vv[i].y;
if(tip >= 3)
cin >> vv[i].z;
}
for(int i = 1; i <= n; ++i)
for(int j = i+1; j <= n; ++j)
{
int dd = abs(vv[i].x - vv[j].x) + abs(vv[i].y - vv[j].y) + abs(vv[i].z - vv[j].z);
if(dd <= d)
++ans;
}
cout << ans << '\n';
}
int v[100002];
void solve1()
{
for(int i = 1; i <= n; ++i)
cin >> v[i];
sort(v+1, v+n+1);
for(int i = 1; i <= n; ++i)
{
int sm = i;
int st = 1;
int dr = i-1;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(v[i] - v[mid] <= d)
sm = mid, dr = mid - 1;
else
st = mid + 1;
}
ans += (i - sm);
}
cout << ans << '\n';
}
pair<int, int> nr[100002];
int aib[400][200002];
vector<int>coord[150002];
void upd(int bu, int pz, int val)
{
for(; pz <= 200000; pz += (pz & (-pz)))
aib[bu][pz] += val;
}
int compute(int bu, int pz)
{
pz = min(pz, 200000);
int ans = 0;
for(; pz > 0; pz -= (pz & (-pz)))
ans += aib[bu][pz];
return ans;
}
int cb(int linie, int col)
{
int ans = 0;
int st = 0;
int dr = coord[linie].size() - 1;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(coord[linie][mid] <= col)
ans = (mid + 1), st = mid + 1;
else
dr = mid - 1;
}
return ans;
}
void solve2()
{
int buk = 400;
for(int i = 1; i <= n; ++i)
{
int x, y;
cin >> x >> y;
nr[i].first = x + y;
nr[i].second = x - y + 100000;
coord[nr[i].first].push_back(nr[i].second);
int nrbuk = nr[i].first / buk + (nr[i].first % buk > 0);
upd(nrbuk, nr[i].second, 1);
}
for(int i = 0; i <= 150000; ++i)
sort(coord[i].begin(), coord[i].end());
for(int i = 1; i <= n; ++i)
{
int st = max(1, nr[i].first - d);
int sf = min(150000, nr[i].first + d);
int nrbuk = nr[i].first / buk + (nr[i].first % buk > 0);
upd(nrbuk, nr[i].second, -1);
while(st <= sf && st <= nrbuk * buk)
{
if(st == nr[i].first)
--ans;
ans += cb(st, nr[i].second + d) - cb(st, nr[i].second - d - 1);
++st;
}
while(st + buk - 1 <= sf)
{
++nrbuk;
ans += compute(nrbuk, nr[i].second + d) - compute(nrbuk, nr[i].second - d - 1);
st += buk;
}
while(st <= sf)
{
if(st == nr[i].first)
--ans;
ans += cb(st, nr[i].second + d) - cb(st, nr[i].second - d - 1);
++st;
}
upd(nrbuk, nr[i].second, 1);
}
cout << ans / 2 << '\n';
}
void solve3()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tip >> n >> d >> m;
if(tip == 1)
solve1();
else
if(n <= 20000)
solvesmall();
else
if(tip == 2)
solve2();
else
else
if(tip == 3)
solve3();
return 0;
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:151:17: error: expected primary-expression before 'else'
else
^~~~
