| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786537 |
2023-07-18T08:53:00 Z |
danikoynov |
Pairs (IOI07_pairs) |
C++14 |
|
252 ms |
35364 KB |
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct point
{
int x, y, z, f;
point(int _x = 0, int _y = 0, int _z = 0, int _f = 0)
{
x = _x;
y = _y;
z = _z;
f = _f;
}
} p[maxn], s[maxn];
bool cmp(point p1, point p2)
{
if (p1.x != p2.x)
return p1.x < p2.x;
if (p1.y != p2.y)
return p1.y < p2.y;
if (p1.z != p2.z)
return p1.z < p2.z;
return p1.f < p2.f;
}
const int max_size = 150010;
struct fenwick_1d
{
int fen[max_size];
fenwick_1d()
{
memset(fen, 0, sizeof(fen));
}
void update(int pos, int val)
{
for (int i = pos; i < max_size; i += (i & -i))
fen[i] += val;
}
int query(int pos)
{
if (pos >= max_size)
pos = max_size - 1;
if (pos < 0)
pos = 0;
///cout << pos << endl;
int sum = 0;
for (int i = pos; i > 0; i -= (i & -i))
sum += fen[i]; ///cout << "step " << i << " " << fen[i] << endl;
///cout << "value " << sum << endl;
return sum;
}
};
const int maxm = 301;
int bit[maxm][maxm][maxm];
void update3d(int x, int y, int z, int val)
{
for (int i = x; i < maxm; i += (i & -i))
for (int j = y; j < maxm; j += (j & -j))
for (int k = z; k < maxm; k += (k & -k))
bit[i][j][k] += val;
}
int query3d(int x, int y, int z)
{
int sum = 0;
if (x >= maxm)
x = maxm - 1;
if (x < 0)
x = 0;
if (y >= maxm)
y = maxm - 1;
if (y < 0)
y = 0;
if (z >= maxm)
z = maxm - 1;
if (z < 0)
z = 0;
for (int i = x; i > 0; i -= (i & -i))
for (int j = y; j > 0; j -= (j & -j))
for (int k = z; k > 0; k -= (k & -k))
sum += bit[i][j][k];
return sum;
}
int b, n, d, m;
void solve()
{
cin >> b >> n >> d >> m;
for (int i = 1; i <= n; i ++)
{
cin >> p[i].x;
if (b >= 2)
cin >> p[i].y;
if (b == 3)
cin >> p[i].z;
}
if (b == 1)
{
sort(p + 1, p + n + 1, cmp);
int pt = 1;
ll ans = 0;
for (int i = 1; i <= n; i ++)
{
while(p[i].x - p[pt].x > d)
pt ++;
///cout << i << " : " << p[i].x << " " << pt << endl;
ans += (ll)(i - pt);
}
cout << ans << endl;
}
else if (b == 2)
{
for (int i = 1; i <= n; i ++)
{
s[i].x = p[i].x - p[i].y;
s[i].y = p[i].x + p[i].y;
}
ll ans = 0;
/**for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
if (abs(s[i].x - s[j].x) <= d && abs(s[i].y - s[j].y) <= d)
ans ++;*/
fenwick_1d tree;
sort(s + 1, s + n + 1, cmp);
int pt = 1;
for (int i = 1; i <= n; i ++)
{
tree.update(s[i].y, 1);
while(s[i].x - s[pt].x > d)
{
tree.update(s[pt].y, -1);
pt ++;
}
ll len = tree.query(s[i].y + d) - tree.query(s[i].y - d - 1);
ans = ans + (len - 1);
}
cout << ans << endl;
}
else
{
for (int i = 1; i <= n; i ++)
{
s[i].x = p[i].x - p[i].y - p[i].z;
s[i].y = p[i].x + p[i].y - p[i].z + 75;
s[i].z = p[i].x - p[i].y + p[i].z + 75;
s[i].f = p[i].x + p[i].y + p[i].z + 75;
}
ll ans = 0;
/**for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
if (abs(s[i].x - s[j].x) <= d && abs(s[i].y - s[j].y) <= d &&
abs(s[i].z - s[j].z) <= d && abs(s[i].f - s[j].f) <= d)
ans ++;*/
sort(s + 1, s + n + 1, cmp);
int pt = 1;
for (int i = 1; i <= n; i ++)
{
while(s[i].x - s[pt].x > d)
{
update3d(s[pt].y, s[pt].z, s[pt].f, - 1);
pt ++;
}
ll len = query3d(s[i].y + d, s[i].z + d, s[i].f + d);
///cout << i << " : " << pt << " " << query3d(maxm, maxm, maxm) << " " << len << endl;
///cout << s[i].x << " " << s[i].y << " " << s[i].z << " " << s[i].f << endl;
len = len - query3d(s[i].y - d - 1, s[i].z + d, s[i].f + d);
len = len - query3d(s[i].y + d, s[i].z - d - 1, s[i].f + d);
len = len - query3d(s[i].y + d, s[i].z + d, s[i].f - d - 1);
len = len + query3d(s[i].y - d - 1, s[i].z - d - 1, s[i].f + d);
len = len + query3d(s[i].y - d - 1, s[i].z + d, s[i].f - d - 1);
len = len + query3d(s[i].y + d, s[i].z - d - 1, s[i].f - d - 1);
len = len - query3d(s[i].y - d - 1, s[i].z - d - 1, s[i].f - d - 1);
ans = ans + len;
update3d(s[i].y, s[i].z, s[i].f, 1);
}
cout << ans << endl;
}
}
int main()
{
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
4012 KB |
Output is correct |
| 2 |
Correct |
42 ms |
4008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
36 ms |
3924 KB |
Output is correct |
| 3 |
Correct |
43 ms |
4008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
4012 KB |
Output is correct |
| 2 |
Correct |
38 ms |
3924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
4044 KB |
Output is correct |
| 2 |
Correct |
48 ms |
3924 KB |
Output is correct |
| 3 |
Correct |
47 ms |
3924 KB |
Output is correct |
| 4 |
Correct |
45 ms |
3924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
64 ms |
4004 KB |
Output is correct |
| 3 |
Correct |
66 ms |
3924 KB |
Output is correct |
| 4 |
Correct |
56 ms |
3924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
18940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
18900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
5148 KB |
Output is correct |
| 2 |
Correct |
109 ms |
5192 KB |
Output is correct |
| 3 |
Correct |
111 ms |
5204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
24628 KB |
Output is correct |
| 2 |
Correct |
181 ms |
25452 KB |
Output is correct |
| 3 |
Correct |
105 ms |
25532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
34540 KB |
Output is correct |
| 2 |
Correct |
252 ms |
35364 KB |
Output is correct |
| 3 |
Correct |
116 ms |
35304 KB |
Output is correct |
