#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define arr array<int, 2>
int N = 1<<18;
int M = 1<<17;
vector<vector<arr>> bin;
vector<int> counter;
vector<vector<int>> upd;
int go(int a, int b, int d)
{
if (bin[a][b][d]==-1)
{
upd[a].push_back(upd[a][b]-1);
bin[a].push_back({-1, -1});
bin[a][b][d] = counter[a];
counter[a]++;
}
return bin[a][b][d];
}
void update(int a, int b)
{
a += N;
while (a)
{
int curr = 0;
int bb = b;
for (int i = 17; i >= 0; i--)
{
upd[a][curr]++;
if (bb>=(1<<i))
{
bb -= 1<<i;
curr = go(a, curr, 1);
}
else curr = go(a, curr, 0);
}
upd[a][curr]++;
a/=2;
}
}
ll ac2d(int a, int curr, int l, int r, int x, int y)
{
if (r <=x || l >= y) return 0;
if (l >= x && r <= y)
{
return upd[a][curr];
}
int m = (l+r)/2;
ll sol = 0;
if (bin[a][curr][0]!=-1) sol += ac2d(a, bin[a][curr][0], l, m, x, y);
if (bin[a][curr][1]!=-1) sol += ac2d(a, bin[a][curr][1], m, r, x, y);
return sol;
}
ll acc(int curr, int l, int r, int a, int b, int x, int y)
{
if (r <=a || l >= b) return 0;
if (l >= a && r <= b)
{
return ac2d(curr, 0, 0, N, x, y);
}
int m = (l+r)/2;
return acc(curr*2, l, m, a, b, x, y)+ acc(curr*2+1, m, r, a, b, x, y);
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int b, n, d, m;
cin >> b >> n >> d >> m;
if (b == 1)
{
vector<int> nums(n);
for (int i =0; i < n; i++) cin >> nums[i];
sort(nums.begin(), nums.end());
ll sol = 0;
queue<int> q;
for (int i = 0; i < n; i++)
{
while (q.size() && nums[i]-q.front()> d) q.pop();
sol += q.size();
q.push(nums[i]);
}
cout << sol;
}
else if (b==2)
{
bin.assign(2*N, vector<arr>(1, {-1, -1}));
counter.assign(2*N, 1);
upd.assign(2*N, vector<ll>(1, 0));
ll sol = 0;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
sol += acc(1, 0, N, x+y-d, x+y+d+1, x-y+M-d-1, x-y+M+d);
update(x+y, x-y+M);
}
cout << sol;
}
return 0;
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:107:41: error: no matching function for call to 'std::vector<std::vector<int> >::assign(int, std::vector<long long int>)'
107 | upd.assign(2*N, vector<ll>(1, 0));
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from pairs.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:749:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
749 | assign(size_type __n, const value_type& __val)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:749:47: note: no known conversion for argument 2 from 'std::vector<long long int>' to 'const value_type&' {aka 'const std::vector<int>&'}
749 | assign(size_type __n, const value_type& __val)
| ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >]'
768 | assign(_InputIterator __first, _InputIterator __last)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note: template argument deduction/substitution failed:
pairs.cpp:107:41: note: deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<long long int>')
107 | upd.assign(2*N, vector<ll>(1, 0));
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from pairs.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:794:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >]'
794 | assign(initializer_list<value_type> __l)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:794:7: note: candidate expects 1 argument, 2 provided
