| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 292165 |
2020-09-06T13:12:05 Z |
Kastanda |
Pairs (IOI07_pairs) |
C++11 |
|
2672 ms |
99536 KB |
// M
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
template < typename T >
using ordered_set = tree < T , null_type , less < T > , rb_tree_tag, tree_order_statistics_node_update >;
const int N = 100005, MX2D = 75005, MX3D = 79;
int n, m, d, Mxd, ts, B[N], F[MX3D][MX3D][MX3D * 3];
vector < int > A[N];
ordered_set < ll > S2D[MX2D];
inline void Add2D(int a, int val)
{
ll vl = val * (ll)(1e6) + ts; ts ++;
for (a ++; a < MX2D; a += a & - a)
S2D[a].insert(vl);
}
inline int Count2D(int a, int val)
{
int rt = 0;
ll vl = val * (ll)(1e6) - 1;
for (; a; a -= a & - a)
rt += (int)S2D[a].size() - S2D[a].order_of_key(vl);
return rt;
}
inline void Add3D(int a, int b, int val)
{
val = MX3D * 3 - val - 3;
for (a ++; a < MX3D; a += a & - a)
for (int d = b + 1; d < MX3D; d += d & - d)
for (int i = val; i < MX3D * 3; i += i & - i)
F[a][d][i] ++;
}
inline int Count3D(int a, int b, int val)
{
int rt = 0;
val = MX3D * 3 - val - 3;
for (; a; a -= a & - a)
for (int d = b; d; d -= d & - d)
for (int i = val; i; i -= i & - i)
rt += F[a][d][i];
return rt;
}
int main()
{
scanf("%d%d%d%d", &d, &n, &Mxd, &m);
if (d == 1)
{
ll tot = 0;
for (int i = 1; i <= n; i ++)
scanf("%d", &B[i]);
sort(B + 1, B + n + 1);
for (int i = 1; i <= n; i ++)
tot += (int)(upper_bound(B + 1, B + n + 1, B[i] + Mxd) - B) - i - 1;
return !printf("%lld\n", tot);
}
for (int i = 1; i <= n; i ++)
{
A[i] = vector < int > (d, 0);
for (int j = 0; j < d; j ++)
scanf("%d", &A[i][j]);
}
sort(A + 1, A + n + 1);
if (d == 2)
{
ll tot = 0;
for (int wy = 0; wy < 2; wy ++)
{
for (int i = 1; i <= n; i ++)
{
int vl = A[i][0] + A[i][1];
tot += Count2D(A[i][1] + wy, vl - Mxd);
Add2D(A[i][1], vl);
}
for (int i = 1; i <= n; i ++)
A[i][1] = MX2D - A[i][1] - 1;
for (int i = 0; i < MX2D; i ++)
S2D[i].clear();
}
return !printf("%lld\n", tot);
}
ll tot = 0;
for (int wy = 0; wy < 2; wy ++)
{
for (int wz = 0; wz < 2; wz ++)
{
for (int i = 1; i <= n; i ++)
{
int vl = A[i][0] + A[i][1] + A[i][2];
tot += Count3D(A[i][1] + wy, A[i][2] + wz, vl - Mxd);
Add3D(A[i][1], A[i][2], vl);
}
for (int i = 1; i <= n; i ++)
A[i][2] = 76 - A[i][2];
memset(F, 0, sizeof(F));
}
for (int i = 1; i <= n; i ++)
A[i][1] = 76 - A[i][1];
}
return !printf("%lld\n", tot);
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
48 | scanf("%d%d%d%d", &d, &n, &Mxd, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
pairs.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
63 | scanf("%d", &A[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
10112 KB |
Output is correct |
| 2 |
Correct |
32 ms |
10112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
10104 KB |
Output is correct |
| 2 |
Correct |
39 ms |
10232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
39 ms |
10156 KB |
Output is correct |
| 3 |
Correct |
37 ms |
10112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
10240 KB |
Output is correct |
| 2 |
Correct |
16 ms |
10368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1273 ms |
99536 KB |
Output is correct |
| 2 |
Correct |
1207 ms |
99320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2214 ms |
88436 KB |
Output is correct |
| 2 |
Correct |
2344 ms |
88584 KB |
Output is correct |
| 3 |
Correct |
1879 ms |
90024 KB |
Output is correct |
| 4 |
Correct |
1928 ms |
88712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2672 ms |
68976 KB |
Output is correct |
| 2 |
Correct |
2505 ms |
69004 KB |
Output is correct |
| 3 |
Correct |
1242 ms |
71032 KB |
Output is correct |
| 4 |
Correct |
1817 ms |
76788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
15488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
18680 KB |
Output is correct |
| 2 |
Correct |
150 ms |
18808 KB |
Output is correct |
| 3 |
Incorrect |
136 ms |
19192 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
18680 KB |
Output is correct |
| 2 |
Incorrect |
212 ms |
18808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
18680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
