This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
class Seg{
vector<ll> st;
int len = 1;
public:
Seg(int n){
while(len < n) len *= 2;
st.resize(len * 2, 0);
}
void add(int idx, ll val, int i, int s, int e){
if(idx < s || idx >= e) return;
if(idx == s && s + 1 == e){
st[i] += val;
return;
}
add(idx, val, i * 2, s, (s + e) / 2);
add(idx, val, i * 2 + 1, (s + e) / 2, e);
st[i] = st[i * 2] + st[i * 2 + 1];
}
void add(int idx, ll val){
add(idx, val, 1, 0, len);
}
ll qry(int l, int r, int i, int s, int e){
if(l >= e || s >= r) return 0;
if(l <= s && e <= r) return st[i];
return qry(l, r, i * 2, s, (s + e) / 2) + qry(l, r, i * 2 + 1, (s + e) / 2, e);
}
ll qry(int l, int r){
return qry(l, r, 1, 0, len);
}
};
vector<int> coords;
int cmpr(int x){
return lower_bound(all(coords), x) - coords.begin();
}
int main()
{
int b, n, d, m; cin >> b >> n >> d >> m;
if(b == 1){
vector<pair<int, int>> q;
vector<int> ad;
Seg st(m + 1);
for (int i = 0; i < n; i++) {
int a; cin >> a;
ad.push_back(a);
q.push_back({a - d, a + d + 1});
coords.push_back(a);
coords.push_back(a - d);
coords.push_back(a + d + 1);
}
sort(all(coords));
for (auto &i : ad)
st.add(cmpr(i), 1);
ll res = 0;
for (auto &[f, t] : q)
res += st.qry(cmpr(f), cmpr(t)) - 1;
cout << res / 2 << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |