| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 152962 |
2019-09-10T18:53:01 Z |
luciocf |
Pairs (IOI07_pairs) |
C++14 |
|
284 ms |
4856 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 4e5+10;
const int add1 = 2e5+10;
const int maxn2 = 455;
const int add2 = 230;
struct Pt
{
int x, y, z;
} p[maxn];
bool comp(Pt a, Pt b)
{
return a.x < b.x;
}
pii a[maxn];
int bit_1d[2][maxn];
int bit_2d[3][455][455];
void upd_1d(int x, int v, int q)
{
if (!x) return;
for (; x < maxn; x += (x&-x))
bit_1d[q][x] += v;
}
int soma_1d(int x, int q)
{
int ans = 0;
for (; x > 0; x -= (x&-x))
ans += bit_1d[q][x];
return ans;
}
void upd_2d(int x, int y, int v, int q)
{
for (int i = x; i < maxn2; i += (i&-i))
for (int j = y; j < maxn2; j += (j&-j))
bit_2d[q][i][j] += v;
}
int soma_2d(int x, int y, int q)
{
int ans = 0;
for (int i = x; i > 0; i -= (i&-i))
for (int j = y; j > 0; j -= (j&-j))
ans += bit_2d[q][i][j];
return ans;
}
long long solve_1(void)
{
int n, d, m;
scanf("%d %d %d", &n, &d, &m);
int x[n+1];
for (int i = 1; i <= n; i++)
scanf("%d", &x[i]);
sort(x+1, x+n+1);
long long ans = 0;
int l = 1, r = 2;
while (l <= n && r <= n)
{
if (l != r && x[r]-x[l] <= d)
ans += 1ll*(r-l);
if (x[r]-x[l] <= d) r++;
else l++;
}
return ans;
}
long long solve_2(void)
{
int n, D, m;
scanf("%d %d %d", &n, &D, &m);
for (int i = 1; i <= n; i++)
scanf("%d %d", &a[i].first, &a[i].second);
sort(a+1, a+n+1);
long long ans = 0;
int ptr = 1;
upd_1d(a[1].first+a[1].second+add1, 1, 0);
upd_1d(a[1].second+add1, 1, 1);
for (int i = 2; i <= n; i++)
{
while (ptr < i && a[i].first-a[ptr].first > D)
{
upd_1d(a[ptr].first+a[ptr].second+add1, -1, 0);
upd_1d(a[ptr].second+add1, -1, 1);
ptr++;
}
if (i != ptr)
{
ans += 1ll*(soma_1d(maxn-1, 0)-soma_1d(a[i].first+a[i].second-D-1+add1, 0));
ans -= 1ll*(soma_1d(maxn-1, 1)-soma_1d(a[i].second+add1, 1));
}
upd_1d(a[i].first+a[i].second+add1, 1, 0);
upd_1d(a[i].second+add1, 1, 1);
}
memset(bit_1d, 0, sizeof bit_1d);
ptr = 1;
upd_1d(a[1].first-a[1].second+add1, 1, 0);
upd_1d(a[1].second+add1, 1, 1);
for (int i = 2; i <= n; i++)
{
while (ptr < i && a[i].first-a[ptr].first > D)
{
upd_1d(a[ptr].first-a[ptr].second+add1, -1, 0);
upd_1d(a[ptr].second+add1, -1, 1);
ptr++;
}
if (i != ptr)
{
ans += 1ll*(soma_1d(maxn-1, 0)-soma_1d(a[i].first-a[i].second-D-1+add1, 0));
ans -= 1ll*soma_1d(a[i].second+add1, 1);
}
upd_1d(a[i].first-a[i].second+add1, 1, 0);
upd_1d(a[i].second+add1, 1, 1);
}
return ans;
}
int get_rect(int x1, int y1, int x2, int y2, int q)
{
return (soma_2d(x2, y2, q)-soma_2d(x1-1, y2, q)-soma_2d(x2, y1-1, q)+soma_2d(x1-1, y1-1, q));
}
long long solve_3(void)
{
int n, D, m;
scanf("%d %d %d", &n, &D, &m);
for (int i = 1; i <= n; i++)
scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
sort(p+1, p+n+1, comp);
long long ans = 0;
int ptr = 1;
upd_2d(p[1].y+add2, p[1].x+p[1].y+p[1].z+add2, 1, 0);
upd_2d(p[1].z+add2, p[1].x+p[1].y+p[1].z+add2, 1, 1);
upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);
for (int i = 2; i <= n; i++)
{
while (ptr < i && p[i].x-p[ptr].x > D)
{
upd_2d(p[ptr].y+add2, p[ptr].x+p[ptr].y+p[ptr].z+add2, -1, 0);
upd_2d(p[ptr].z+add2, p[ptr].x+p[ptr].y+p[ptr].z+add2, -1, 1);
upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
ptr++;
}
if (i != ptr)
{
ans += 1ll*get_rect(1+add2, p[i].x+p[i].y+p[i].z-D+add2, p[i].y+add2, maxn2-1, 0);
ans -= 1ll*get_rect(p[i].z+1+add2, p[i].x+p[i].y+p[i].z-D+add2, maxn2-1, maxn2-1, 1);
ans += 1ll*get_rect(p[i].y+1+add2, p[i].z+1+add2, maxn2-1, maxn2-1, 2);
}
upd_2d(p[i].y+add2, p[i].x+p[i].y+p[i].z+add2, 1, 0);
upd_2d(p[i].z+add2, p[i].x+p[i].y+p[i].z+add2, 1, 1);
upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
}
memset(bit_2d, 0, sizeof bit_2d);
ptr = 1;
upd_2d(p[1].y+add2, p[1].x+p[1].y-p[1].z+add2, 1, 0);
upd_2d(p[1].z+add2, p[1].x+p[1].y-p[1].z+add2, 1, 1);
upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);
for (int i = 2; i <= n; i++)
{
while (ptr < i && p[i].x-p[ptr].x > D)
{
upd_2d(p[ptr].y+add2, p[ptr].x+p[ptr].y-p[ptr].z+add2, -1, 0);
upd_2d(p[ptr].z+add2, p[ptr].x+p[ptr].y-p[ptr].z+add2, -1, 1);
upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
ptr++;
}
if (i != ptr)
{
ans += 1ll*get_rect(1+add2, p[i].x+p[i].y-p[i].z-D+add2, p[i].y+add2, maxn2-1, 0);
ans -= 1ll*get_rect(1+add2, p[i].x+p[i].y-p[i].z-D+add2, p[i].z+add2, maxn2-1, 1);
ans += 1ll*get_rect(p[i].y+1+add2, 1+add2, maxn2-1, p[i].z+add2, 2);
}
upd_2d(p[i].y+add2, p[i].x+p[i].y-p[i].z+add2, 1, 0);
upd_2d(p[i].z+add2, p[i].x+p[i].y-p[i].z+add2, 1, 1);
upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
}
memset(bit_2d, 0, sizeof bit_2d);
ptr = 1;
upd_2d(p[1].y+add2, p[1].x-p[1].y+p[1].z+add2, 1, 0);
upd_2d(p[1].z+add2, p[1].x-p[1].y+p[1].z+add2, 1, 1);
upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);
for (int i = 2; i <= n; i++)
{
while (ptr < i && p[i].x-p[ptr].x > D)
{
upd_2d(p[ptr].y+add2, p[ptr].x-p[ptr].y+p[ptr].z+add2, -1, 0);
upd_2d(p[ptr].z+add2, p[ptr].x-p[ptr].y+p[ptr].z+add2, -1, 1);
upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
ptr++;
}
if (i != ptr)
{
ans += 1ll*get_rect(p[i].y+1+add2, p[i].x-p[i].y+p[i].z-D+add2, maxn2-1, maxn2-1, 0);
ans -= 1ll*get_rect(p[i].z+1+add2, p[i].x-p[i].y+p[i].z-D+add2, maxn2-1, maxn2-1, 1);
ans += 1ll*get_rect(1+add2, p[i].z+1+add2, p[i].y+add2, maxn2-1, 2);
}
upd_2d(p[i].y+add2, p[i].x-p[i].y+p[i].z+add2, 1, 0);
upd_2d(p[i].z+add2, p[i].x-p[i].y+p[i].z+add2, 1, 1);
upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
}
memset(bit_2d, 0, sizeof bit_2d);
ptr = 1;
upd_2d(p[1].y+add2, p[1].x-p[1].y-p[1].z+add2, 1, 0);
upd_2d(p[1].z+add2, p[1].x-p[1].y-p[1].z+add2, 1, 1);
upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);
for (int i = 2; i <= n; i++)
{
while (ptr < i && p[i].x-p[ptr].x > D)
{
upd_2d(p[ptr].y+add2, p[ptr].x-p[ptr].y-p[ptr].z+add2, -1, 0);
upd_2d(p[ptr].z+add2, p[ptr].x-p[ptr].y-p[ptr].z+add2, -1, 1);
upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
ptr++;
}
if (i != ptr)
{
ans += 1ll*get_rect(p[i].y+1+add2, p[i].x-p[i].y-p[i].z-D+add2, maxn2-1, maxn2-1, 0);
ans -= 1ll*get_rect(1+add2, p[i].x-p[i].y-p[i].z-D+add2, p[i].z+add2, maxn2-1, 1);
ans += 1ll*get_rect(1+add2, 1+add2, p[i].y+add2, p[i].z+add2, 2);
}
upd_2d(p[i].y+add2, p[i].x-p[i].y-p[i].z+add2, 1, 0);
upd_2d(p[i].z+add2, p[i].x-p[i].y-p[i].z+add2, 1, 1);
upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
}
return ans;
}
int main(void)
{
int b;
scanf("%d", &b);
if (b == 1) printf("%lld\n", solve_1());
else if (b == 2) printf("%lld\n", solve_2());
else printf("%lld\n", solve_3());
}
Compilation message
pairs.cpp: In function 'long long int solve_1()':
pairs.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &d, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x[i]);
~~~~~^~~~~~~~~~~~~
pairs.cpp: In function 'long long int solve_2()':
pairs.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &D, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a[i].first, &a[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'long long int solve_3()':
pairs.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &D, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:297:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
636 KB |
Output is correct |
| 2 |
Correct |
20 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
760 KB |
Output is correct |
| 2 |
Correct |
27 ms |
784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
632 KB |
Output is correct |
| 2 |
Correct |
27 ms |
784 KB |
Output is correct |
| 3 |
Correct |
26 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
4308 KB |
Output is correct |
| 2 |
Correct |
49 ms |
4344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
61 ms |
4228 KB |
Output is correct |
| 3 |
Correct |
64 ms |
4232 KB |
Output is correct |
| 4 |
Correct |
62 ms |
4216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
4220 KB |
Output is correct |
| 2 |
Correct |
68 ms |
4296 KB |
Output is correct |
| 3 |
Correct |
67 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
66 ms |
4216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
4088 KB |
Output is correct |
| 2 |
Correct |
211 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
209 ms |
4584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
284 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
244 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
230 ms |
4820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
3944 KB |
Output is correct |
| 2 |
Correct |
245 ms |
4856 KB |
Output is correct |
| 3 |
Correct |
235 ms |
4856 KB |
Output is correct |
