# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
720153 |
2023-04-07T13:58:10 Z |
marvinthang |
Pairs (IOI07_pairs) |
C++17 |
|
226 ms |
25268 KB |
/*************************************
* author: marvinthang *
* created: 23.08.2022 20:47:40 *
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define div ___div
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define FULL(i) (MASK(i) - 1)
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; }
template <class A, class B> inline bool minimize(A &a, B b) { A eps = 1e-9; if (a > b + eps) { a = b; return true; } return false; }
template <class A, class B> inline bool maximize(A &a, B b) { A eps = 1e-9; if (a + eps < b) { a = b; return true; } return false; }
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const int MAX = 12e6;
int bit[MAX], maxX = 1, maxY = 1, maxZ = 1;
inline int &at(int x, int y, int z) { return bit[((x - 1) * maxY + (y - 1)) * maxZ + z - 1]; }
void update(int xx, int yy, int zz, int val) {
for (int x = xx; x <= maxX; x += x & -x)
for (int y = yy; y <= maxY; y += y & -y)
for (int z = zz; z <= maxZ; z += z & -z)
at(x, y, z) += val;
}
int get(int xx, int yy, int zz) {
int res = 0;
for (int x = xx; x; x &= x - 1)
for (int y = yy; y; y &= y - 1)
for (int z = zz; z; z &= z - 1)
res += at(x, y, z);
return res;
}
int get(int x1, int y1, int z1, int x2, int y2, int z2) {
--x1; --y1; --z1;
maximize(x1, 0);
maximize(y1, 0);
maximize(z1, 0);
minimize(x2, maxX);
minimize(y2, maxY);
minimize(z2, maxZ);
return get(x2, y2, z2)
- get(x1, y2, z2) - get(x2, y1, z2) - get(x2, y2, z1)
+ get(x1, y1, z2) + get(x2, y1, z1) + get(x1, y2, z1)
- get(x1, y1, z1);
}
int B, N, D, M;
struct Item {
int a, b, c, d;
Item(int a = 1, int b = 1, int c = 1, int d = 1): a(a), b(b), c(c), d(d) {}
bool operator < (const Item &other) const {
return a < other.a;
}
} items[(int) 1e5 + 5];
void init(void) {
cin >> B >> N >> D >> M;
if (B == 2) maxX = 2 * M;
else if (B == 3) maxX = maxY = maxZ = 3 * M;
for (int i = 1; i <= N; ++i) {
int x, y, z;
if (B == 1) {
cin >> x;
items[i] = Item(x);
} else if (B == 2) {
cin >> x >> y;
items[i] = Item(x + y - 1, x - y + M);
} else {
cin >> x >> y >> z;
items[i] = Item(x + y + z - 2, x + y - z + M - 1, x - y + z + M - 1, x - y - z + M + M);
}
}
sort(items + 1, items + 1 + N);
}
void process(void) {
long long res = 0;
for (int r = 1, l = 1; r <= N; ++r) {
while (items[r].a - items[l].a > D)
update(items[l].b, items[l].c, items[l].d, -1), ++l;
res += get( items[r].b - D, items[r].c - D, items[r].d - D,
items[r].b + D, items[r].c + D, items[r].d + D);
update(items[r].b, items[r].c, items[r].d, +1);
}
cout << res << '\n';
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
file("nkpairs");
init();
process();
cerr << "Time elapsed: " << TIME << " s.\n";
return (0^0);
}
Compilation message
pairs.cpp: In function 'int main()':
pairs.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:114:2: note: in expansion of macro 'file'
114 | file("nkpairs");
| ^~~~
pairs.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:114:2: note: in expansion of macro 'file'
114 | file("nkpairs");
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
2260 KB |
Output is correct |
2 |
Correct |
16 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2752 KB |
Output is correct |
2 |
Correct |
21 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
2752 KB |
Output is correct |
2 |
Correct |
22 ms |
2756 KB |
Output is correct |
3 |
Correct |
22 ms |
2656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2388 KB |
Output is correct |
2 |
Correct |
2 ms |
2420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2388 KB |
Output is correct |
2 |
Correct |
22 ms |
2456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
2556 KB |
Output is correct |
2 |
Correct |
34 ms |
2664 KB |
Output is correct |
3 |
Correct |
45 ms |
2652 KB |
Output is correct |
4 |
Correct |
33 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
3572 KB |
Output is correct |
2 |
Correct |
58 ms |
3532 KB |
Output is correct |
3 |
Correct |
40 ms |
3540 KB |
Output is correct |
4 |
Correct |
48 ms |
3508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
13512 KB |
Output is correct |
2 |
Correct |
8 ms |
13524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
2496 KB |
Output is correct |
2 |
Correct |
47 ms |
2516 KB |
Output is correct |
3 |
Correct |
33 ms |
2516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
14668 KB |
Output is correct |
2 |
Correct |
138 ms |
14668 KB |
Output is correct |
3 |
Correct |
59 ms |
14676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
25204 KB |
Output is correct |
2 |
Correct |
187 ms |
25236 KB |
Output is correct |
3 |
Correct |
91 ms |
25268 KB |
Output is correct |