CSES — Hotel Queries

__abs's blog

By __abs, history, 17 months ago, In English

Question. I understand how to solve this using Segment Trees.

I saw this solution by pikmike.

Copied here

#include <iostream>
 
using namespace std;
 
#define f() for (i = y = 0; k = i / P, i < n; ++i)
 
main(){
	int P = 450, n, m, x, y, i, k, a[P*P], b[P];
	cin >> n >> m;
	f() cin >> a[i], b[k] = 2e9;
	for(;m--, cin >> x; cout << y << " ")
		f() i%P || !y * b[k] >= x ? y | a[i] < x ? : (a[y = i] -= x, ++y), b[k] = max(i%P ? b[k] : 0, a[i]) : i += P - 1;
}

Can someone explain how this works?

cses, doubt, range query

__abs
17 months ago
1

Comments (1)

Write comment?

h_squared

17 months ago, # |

Divide N hotels into groups of size 450. Just iterate from 1 to N/450 to find first group with required rooms while maintaining group max after each query.

→ Reply