#include <bits/stdc++.h>
using namespace std;
template<typename T>
string tostr(const T& value) {
ostringstream oss;
oss << fixed << setprecision(7);
oss << value;
return oss.str();
}
template<typename... Args>
string fstr(const string& format, Args... args) {
string result = format;
size_t pos = 0;
size_t argIndex = 0;
auto replaceArg = [&](const auto& arg) {
pos = result.find("{}", pos);
if (pos != string::npos) {
result.replace(pos, 2, tostr(arg));
++argIndex;
}
};
(replaceArg(args), ...);
return result;
}
#define int long long
const int INF = LLONG_MAX / 2 - INT_MAX;
const int INFmem = 0x3f3f3f3f'3f3f3f3f;
const int inf = INT_MAX / 2;
const int infmem = 0x3f3f3f3f;
const int maxn = 100005;
const int maxm1 = 75000000;
const int maxm2 = 75000 * 2;
const int maxm3 = 75;
// dynamic segment tree pointers point update and range query for sum
struct ND {
int v; int L, R; ND *l, *r;
ND(int v, int L, int R, ND* l, ND* r) : v(v), L(L), R(R), l(l), r(r) {}
ND() : v(0), L(0), R(0), l(nullptr), r(nullptr) {}
~ND() { delete l; delete r; }
ND* gl() {
if (!l) {
int m = (L + R) >> 1;
l = new ND(v/(R-L+1)*(m-L+1), L, m, nullptr, nullptr);
}
return l;
}
ND* gr() {
if (!r) {
int m = (L + R) >> 1;
r = new ND(v/(R-L+1)*(R-m), m+1, R, nullptr, nullptr);
}
return r;
}
void upd(int K, int V) {
if (L == R) { v += V; return; }
int m = (L + R) >> 1;
if (K <= m) { gl()->upd(K, V); }
else { gr()->upd(K, V); }
v = gl()->v + gr()->v;
}
int qry(int K1, int K2) {
if (K2 < L || R < K1) { return 0; }
if (K1 <= L && R <= K2) { return v; }
int m = (L + R) >> 1;
return gl()->qry(K1, K2) + gr()->qry(K1, K2);
}
};
// binary indexed tree OF NDs, 2d
struct BIT {
ND bit[maxm2 + 1];
void upd(int K1, int K2) {
for ( ; K1 <= maxm2; K1 += K1 & -K1)
bit[K1].upd(K2, 1);
}
int qry(int K11, int K12, int K21, int K22) {
int ret = 0;
for ( ; K12; K12 -= K12 & -K12)
ret += bit[K12].qry(K21, K22);
K11--;
for ( ; K11; K11 -= K11 & -K11)
ret -= bit[K11].qry(K21, K22);
return ret;
}
};
int b, n, d, m;
int ans = 0;
void solve() {
cin >> b >> n >> d >> m;
if (b == 1) {
vector<int> pts(n);
for (int i = 0; i < n; i++)
cin >> pts[i];
ND root = ND(0, 0, maxm1, nullptr, nullptr);
for (auto& i : pts) {
ans += root.qry(max(0ll, i - d), min(maxm1, i + d));
root.upd(i, 1);
}
cout << ans << endl;
} else if (b == 2) {
vector<pair<int,int>> pts(n);
for (int i = 0; i < n; i++)
cin >> pts[i].first >> pts[i].second;
BIT bit; for (int i = 0; i <= maxm2; i++) bit.bit[i] = ND(0, 0, maxm2, nullptr, nullptr);
for (auto& i : pts) {
int a = i.first + i.second, b = maxm2 + i.first - i.second;
ans += bit.qry(max(0ll, a - d), min(maxm2, a + d), max(0ll, b - d), min(maxm2, b + d));
bit.upd(a, b);
}
cout << ans << endl;
} else if (b == 3) {
vector<pair<int,pair<int,int>>> pts(n);
for (int i = 0; i < n; i++)
cin >> pts[i].first >> pts[i].second.first >> pts[i].second.second;
}
}
// #define LOCAL
// #define CODEFORCES
signed main() {
#ifndef LOCAL
cin.tie(nullptr) -> ios::sync_with_stdio(false);
#endif
#ifdef LOCAL
freopen("main.in", "r", stdin);
#endif
int t;
#ifdef CODEFORCES
cin >> t;
#endif
#ifndef CODEFORCES
t=1;
#endif
for (int i = 1; i <= t; i++) {
#ifdef LOCAL
cout << fstr("----- Case {} -----", i) << endl;
auto startTime = clock();
#endif
solve();
#ifdef LOCAL
cout << fstr("RUNTIME: {}", (double)(clock() - startTime)/CLOCKS_PER_SEC) << endl;
cout << fstr("----- END CASE {} -----", i) << endl;
#endif
#ifdef LOCAL
#endif
}
return 0;
}
Compilation message
pairs.cpp: In member function 'long long int ND::qry(long long int, long long int)':
pairs.cpp:72:13: warning: unused variable 'm' [-Wunused-variable]
72 | int m = (L + R) >> 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
10072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
35 ms |
7488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
470 ms |
216324 KB |
Output is correct |
| 2 |
Correct |
208 ms |
105300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
473 ms |
215720 KB |
Output is correct |
| 2 |
Correct |
127 ms |
33620 KB |
Output is correct |
| 3 |
Correct |
74 ms |
13764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
25688 KB |
Output is correct |
| 2 |
Runtime error |
398 ms |
7004 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
388 ms |
11088 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
393 ms |
13912 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
417 ms |
33364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
9048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
9304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
