oj.uz

Submission #720153

# Submission time Handle Problem Language Result Execution time Memory
720153 2023-04-07T13:58:10 Z marvinthang Pairs (IOI07_pairs) C++17
100 / 100
 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");
      |  ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Output is correct
2 Correct 2 ms 1892 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2260 KB Output is correct
2 Correct 16 ms 2260 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2752 KB Output is correct
2 Correct 21 ms 2652 KB Output is correct

Subtask #5
6.0 / 6.0

# 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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 2 ms 2420 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2388 KB Output is correct
2 Correct 22 ms 2456 KB Output is correct

Subtask #8
8.0 / 8.0

# 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

Subtask #9
8.0 / 8.0

# 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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13512 KB Output is correct
2 Correct 8 ms 13524 KB Output is correct

Subtask #11
10.0 / 10.0

# 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

Subtask #12
10.0 / 10.0

# 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

Subtask #13
10.0 / 10.0

# 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