#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n, d, m;
struct TPoint{
int x, y = 0, z = 0;
bool operator < (const TPoint &other){
if (x == other.x){
if (y == other.y) return z < other.z;
return y < other.y;
}
return x < other.x;
}
};
struct TQuery{
int x, y, t;
bool z;
bool operator < (const TQuery &other){
if (x == other.x) return t < other.t;
return x < other.x;
}
};
TPoint a[maxN];
struct Node{
Node *l, *r;
int val;
Node(const int &x) : l(nullptr), r(nullptr), val(0){}
};
Node* root[76];
void create(Node *id){
if (!id->l){
id->l = new Node(0);
}
if (!id->r){
id->r = new Node(0);
}
}
void update(Node *id, int l, int r, int i, int x){
if (r < i || l > i) return;
if (l == r){
id->val += x;
return;
}
int m = (l + r) / 2;
create(id);
update(id->l, l, m, i, x);
update(id->r, m + 1, r, i, x);
id->val = id->l->val + id->r->val;
}
int get(Node *id, int l, int r, int i, int j){
if (r < i || l > j) return 0;
if (i <= l && r <= j){
return id->val;
}
int m = (l + r) / 2;
create(id);
return get(id->l, l, m, i, j) + get(id->r, m + 1, r, i, j);
}
void Init(){
int type; cin >> type >> n >> d >> m;
if (type == 1){
for (int i = 1; i <= n; ++i) cin >> a[i].x;
sort(a + 1, a + n + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i){
TPoint tem = {a[i].x - d, 0, 0};
int k = lower_bound(a + 1, a + n + 1, tem) - a;
ans += i - k;
}
cout << ans;
}
if (type == 2){
ll ans = 0;
vector <TQuery> v;
for (int i = 1; i <= n; ++i){
cin >> a[i].x >> a[i].y;
v.pb({a[i].x - a[i].y, a[i].x + a[i].y, 1});
v.pb({a[i].x - a[i].y + d + 1 , a[i].x + a[i].y, -1});
}
sort(v.begin(), v.end());
root[0] = new Node(0);
for (const auto &i : v){
if (i.t == 1){
ans += get(root[0], 1, 150000, max(1, i.y - d), i.y + d);
}
update(root[0], 1, 150000, i.y, i.t);
}
cout << ans;
}
if (type == 3){
int ans = 0;
vector <TQuery> v[76]; //brute all the surfaces
for (int i = 1; i <= n; ++i){
cin >> a[i].x >> a[i].y >> a[i].z;
v[a[i].z].pb({a[i].x - a[i].y, a[i].x + a[i].y, 1, 1});
v[a[i].z].pb({a[i].x - a[i].y + d + 1, a[i].x + a[i].y, -1});
int zz = a[i].z + 1, j = d - 1;
while (zz <= 75 && j >= 0){
v[zz].pb({a[i].x - a[i].y, a[i].x + a[i].y, 1});
v[zz].pb({a[i].x - a[i].y + j + 1, a[i].x + a[i].y, -1});
++zz; --j;
}
zz = a[i].z - 1; j = d - 1;
while (zz >= 1 && j >= 0){
v[zz].pb({a[i].x - a[i].y, a[i].x + a[i].y, 1});
v[zz].pb({a[i].x - a[i].y + j + 1, a[i].x + a[i].y, - 1});
--zz; --j;
}
}
for (int i = 1; i <= 75; ++i){
sort(v[i].begin(), v[i].end());
root[i] = new Node(0);
}
for (int i = 1; i <= 75; ++i){
for (const auto &j: v[i]){ //O(n * 75?)
if (j.z){
ans += get(root[i], 1, 150, max(1, j.y - d), j.y + d);
}
update(root[i], 1, 150, j.y, j.t);
}
}
cout << ans;
}
}
int main(){
if (fopen(taskname".txt", "r")){
freopen(taskname".txt", "r", stdin);
}
faster
//freopen(taskname.inp, "r", stdin)
//freopen(taskname.out, "w", stdout)
Init();
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | freopen(taskname".txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
17 ms |
1624 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
1600 KB |
Output is correct |
| 2 |
Correct |
38 ms |
1504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
26 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
30 ms |
1620 KB |
Output is correct |
| 3 |
Correct |
22 ms |
1620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2388 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
5760 KB |
Output is correct |
| 2 |
Correct |
91 ms |
6220 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
124 ms |
5740 KB |
Output is correct |
| 2 |
Correct |
108 ms |
6476 KB |
Output is correct |
| 3 |
Correct |
116 ms |
6476 KB |
Output is correct |
| 4 |
Correct |
108 ms |
6476 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
171 ms |
12640 KB |
Output is correct |
| 2 |
Correct |
172 ms |
14564 KB |
Output is correct |
| 3 |
Correct |
134 ms |
8172 KB |
Output is correct |
| 4 |
Correct |
114 ms |
7916 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
3996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
117 ms |
11120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
872 ms |
66996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1937 ms |
155468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
