#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
//#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
struct nush
{
int x;
int y;
int z;
};
nush v[100005];
int a[100005];
vector<int> x[80][150005];///pentru fiecare x, avem y-urile care apar
class MST
{
public:
vector<int> aint[600005];
void build(int l, int r, int val, int nivel)
{
if (l==r)
{
for (auto z : x[nivel][l])
aint[val].push_back(z);///SORTEAZA X INAINTE
return;
}
int mid;
mid=(l+r)/2;
build(l,mid,val*2,nivel);
build(mid+1,r,val*2+1,nivel);
int il,ir,lv,rv;
il=0;
ir=0;
while (il<aint[val*2].size() && ir<aint[val*2+1].size())
{
lv=aint[val*2][il];
rv=aint[val*2+1][ir];
if (lv<rv)
{
aint[val].push_back(lv);
il++;
}
else
{
aint[val].push_back(rv);
ir++;
}
}
while (il<aint[val*2].size())
{
lv=aint[val*2][il];
aint[val].push_back(lv);
il++;
}
while (ir<aint[val*2+1].size())
{
rv=aint[val*2+1][ir];
aint[val].push_back(rv);
ir++;
}
}
int query(int l, int r, int val, int qa, int qb, int x)///strict mai mic
{
if (qa<=l && r<=qb)
{
int r,pas;
r=-1;
pas=(1<<17);
while (pas)
{
if (r+pas<aint[val].size() && aint[val][r+pas]<x)
r+=pas;
pas=pas/2;
}
return r+1;
}
int mid,ans;
ans=0;
mid=(l+r)/2;
if (qa<=mid)
ans+=query(l,mid,val*2,qa,qb,x);
if (qb>mid)
ans+=query(mid+1,r,val*2+1,qa,qb,x);
return ans;
}
} mbappe[80];
signed main()
{
/*
ifstream fin("camere.in");
ofstream fout("camere.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int b,n,m,d,i,ans,l,r,pas,lim,qa,qb,cx,cy,cd,j;
cin >> b >> n >> d >> m;
if (b==1)
{
for (i=1; i<=n; i++)
{
cin >> a[i];
}
sort(a+1,a+1+n);
ans=0;
for (i=1; i<=n; i++)
{
l=0;
lim=a[i]-d;
pas=(1<<17);
while (pas)
{
if (l+pas<=n && a[l+pas]<lim)
l+=pas;
pas=pas/2;
}
l++;
r=0;
lim=a[i]+d;
pas=(1<<17);
while (pas)
{
if (r+pas<=n && a[r+pas]<=lim)
r+=pas;
pas=pas/2;
}
ans+=r-l+1-1;
}
cout << ans/2;
}
else if (b==2)///de aici incepe nebunia
{
for (i=1; i<=n; i++)
{
cin >> v[i].x >> v[i].y;
cx=v[i].x;
cy=v[i].y;
v[i].x=cx+cy;
v[i].y=cx-cy;
x[1][v[i].x].push_back(v[i].y);
}
for (i=1; i<=2*m; i++)
sort(x[1][i].begin(),x[1][i].end());
mbappe[1].build(1,2*m,1,1);
ans=0;
for (i=1; i<=n; i++)
{
qa=max(1LL,v[i].x-d);
qb=min(2*m,v[i].x+d);
r=mbappe[1].query(1,2*m,1,qa,qb,v[i].y+d+1);
l=mbappe[1].query(1,2*m,1,qa,qb,v[i].y-d);
ans+=r-l-1;
}
cout << ans/2;
}
else
{
for(i=1; i<=n; i++)
{
cin >> v[i].x >> v[i].y >> v[i].z;
cx=v[i].x;
cy=v[i].y;
v[i].x=cx+cy;
v[i].y=cx-cy;
x[v[i].z][v[i].x].push_back(v[i].y);
}
for (j=1; j<=m; j++)
{
for (i=1; i<=2*m; i++)
sort(x[j][i].begin(),x[j][i].end());
}
for (j=1; j<=m; j++)
mbappe[j].build(1,2*m,1,j);
ans=0;
cd=d;
for (i=1; i<=n; i++)
{
d=cd;
qa=max(1LL,v[i].x-d);
qb=min(2*m,v[i].x+d);
r=mbappe[v[i].z].query(1,2*m,1,qa,qb,v[i].y+d+1);
l=mbappe[v[i].z].query(1,2*m,1,qa,qb,v[i].y-d);
ans+=r-l-1;
for (j=v[i].z-1; j>=1 && d>=1; j--)
{
d--;
qa=max(1LL,v[i].x-d);
qb=min(2*m,v[i].x+d);
r=mbappe[j].query(1,2*m,1,qa,qb,v[i].y+d+1);
l=mbappe[j].query(1,2*m,1,qa,qb,v[i].y-d);
ans+=r-l;
}
d=cd;
for (j=v[i].z+1;j<=m && d>=1;j++)
{
d--;
qa=max(1LL,v[i].x-d);
qb=min(2*m,v[i].x+d);
r=mbappe[j].query(1,2*m,1,qa,qb,v[i].y+d+1);
l=mbappe[j].query(1,2*m,1,qa,qb,v[i].y-d);
ans+=r-l;
}
}
cout << ans/2;
}
return 0;
}
Compilation message (stderr)
pairs.cpp: In function 'int main()':
pairs.cpp:163:19: error: no matching function for call to 'max(long long int, int)'
163 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from pairs.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
pairs.cpp:163:19: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
163 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
pairs.cpp:163:19: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
163 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
pairs.cpp:163:19: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
163 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
pairs.cpp:163:19: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
163 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
pairs.cpp:194:19: error: no matching function for call to 'max(long long int, int)'
194 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
pairs.cpp:194:19: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
194 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
pairs.cpp:194:19: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
194 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
pairs.cpp:194:19: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
194 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
pairs.cpp:194:19: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
194 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
pairs.cpp:202:23: error: no matching function for call to 'max(long long int, int)'
202 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
pairs.cpp:202:23: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
202 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
pairs.cpp:202:23: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
202 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
pairs.cpp:202:23: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
202 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
pairs.cpp:202:23: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
202 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
pairs.cpp:212:23: error: no matching function for call to 'max(long long int, int)'
212 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
pairs.cpp:212:23: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
212 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
pairs.cpp:212:23: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
212 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
pairs.cpp:212:23: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
212 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
pairs.cpp:212:23: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
212 | qa=max(1LL,v[i].x-d);
| ~~~^~~~~~~~~~~~~~