# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
453208 |
2021-08-04T09:04:12 Z |
prvocislo |
Pairs (IOI07_pairs) |
C++17 |
|
504 ms |
22120 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
typedef long long ll;
using namespace std;
const int maxn = 1.5e5 + 5;
vector<int> st[maxn * 2];
void upd(int x, int y)
{
for (x += maxn; x > 0; x >>= 1) st[x].push_back(y);
}
int query1d(int y1, int y2, int vr) { return upper_bound(st[vr].begin(), st[vr].end(), y2) - lower_bound(st[vr].begin(), st[vr].end(), y1); }
int query(int x1, int y1, int x2, int y2)
{
x1 = max(x1, 0), x2 = min(x2, maxn - 1);
int ans = 0;
for (x1 += maxn, x2 += maxn + 1; x1 < x2; x1 >>= 1, x2 >>= 1)
{
if (x1 & 1) ans += query1d(y1, y2, x1++);
if (x2 & 1) ans += query1d(y1, y2, --x2);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int b, n, d, m;
cin >> b >> n >> d >> m;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++)
{
if (b == 1) cin >> y[i];
else
{
int x1, y1; cin >> x1 >> y1;
x[i] = x1 + y1, y[i] = x1 - y1;
}
upd(x[i], y[i]);
}
for (int i = 0; i < maxn * 2; i++) sort(st[i].begin(), st[i].end());
ll ans = 0;
for (int i = 0; i < n; i++)
{
ans += query(x[i] - d, y[i] - d, x[i] + d, y[i] + d);
}
cout << (ans - n) / 2 << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7244 KB |
Output is correct |
2 |
Correct |
6 ms |
7324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
15292 KB |
Output is correct |
2 |
Correct |
157 ms |
15364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
15356 KB |
Output is correct |
2 |
Correct |
191 ms |
15356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
15372 KB |
Output is correct |
2 |
Correct |
203 ms |
16228 KB |
Output is correct |
3 |
Correct |
204 ms |
16248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7628 KB |
Output is correct |
2 |
Correct |
8 ms |
7628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
16252 KB |
Output is correct |
2 |
Correct |
138 ms |
16100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
286 ms |
16916 KB |
Output is correct |
2 |
Correct |
269 ms |
17016 KB |
Output is correct |
3 |
Correct |
279 ms |
17032 KB |
Output is correct |
4 |
Correct |
291 ms |
16848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
20968 KB |
Output is correct |
2 |
Correct |
470 ms |
22120 KB |
Output is correct |
3 |
Correct |
250 ms |
18904 KB |
Output is correct |
4 |
Correct |
256 ms |
18784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
7372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
115 ms |
16396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
211 ms |
16152 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
245 ms |
16228 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |