Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //----------------------------------- DEBUG -----------------------------------
- #define sim template < class c
- #define ris return * this
- #define dor > debug & operator <<
- #define eni(x) sim > typename \
- enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
- sim > struct rge { c b, e; };
- sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
- sim > auto dud(c* x) -> decltype(cerr << *x, 0);
- sim > char dud(...);
- struct debug {
- #ifdef LOCAL
- ~debug() { cerr << endl; }
- eni(!=) cerr << boolalpha << i; ris; }
- eni(==) ris << range(begin(i), end(i)); }
- sim, class b dor(pair < b, c > d) {
- ris << "(" << d.first << ", " << d.second << ")";
- }
- sim dor(rge<c> d) {
- *this << "[";
- for (auto it = d.b; it != d.e; ++it)
- *this << ", " + 2 * (it == d.b) << *it;
- ris << "]";
- }
- #else
- sim dor(const c&) { ris; }
- #endif
- };
- #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
- //----------------------------------- END DEBUG --------------------------------
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #define trav(a,x) for (auto& a : x)
- #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
- //----------------------------------- DEFINES -----------------------------------
- #define sz(x) (int)(x).size()
- #define mp make_pair
- #define eb emplace_back
- #define pb push_back
- #define lb lower_bound
- #define ub upper_bound
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define ins insert
- #define nl '\n'
- //----------------------------------- END DEFINES --------------------------------
- //-------------------------- CUSTOM UNORDERED MAP HASH ---------------------------
- struct custom_hash{
- static uint64_t splitmix64(uint64_t x){
- x += 0x9e3779b97f4a7c15;
- x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
- x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
- return x ^ (x >> 31);
- }
- size_t operator()(uint64_t a) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- return splitmix64(a + FIXED_RANDOM);
- }
- template<class T> size_t operator()(T a) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- hash<T> x;
- return splitmix64(x(a) + FIXED_RANDOM);
- }
- template<class T, class H> size_t operator()(pair<T, H> a) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- hash<T> x;
- hash<H> y;
- return splitmix64(x(a.first) * 37 + y(a.second) + FIXED_RANDOM);
- }
- };
- template<class T, class H>using umap=unordered_map<T,H,custom_hash>;
- //----------------------- CUSTOM UNORDERED MAP HASH END--------------------------
- const int maxN = 1e9;
- void run_cases() {
- int n,k;
- cin >> n >> k;
- assert(1 <= n and n <= int(1e5));
- assert(1 <= k and k <= maxN);
- int max_people = -1;
- vector<pair<int,int>> pos;
- for(int i=0;i<n;i++) {
- int x,y;
- cin >> x >> y;
- assert(x < y);
- assert(1 <= x and x <= maxN);
- assert(1 <= y and y <= maxN);
- pos.emplace_back(x,y);
- }
- sort(all(pos));
- assert(int(pos.size()) == n);
- umap<int,int> cnt;
- priority_queue<int, vector<int>, greater<int> > ins, outs;
- umap<int, bool> marked;
- for(int i=0;i<n;i++) {
- int in, out;
- tie(in, out) = pos[i];
- while(!ins.empty() and ins.top() < in) {
- if(!marked[ins.top()]) {
- cnt[in] += cnt[ins.top()];
- marked[ins.top()] = true;
- }
- ins.pop();
- }
- if(ins.empty() or ins.top() != in) {
- ins.push(in);
- }
- while(!outs.empty() and outs.top() < in) {
- if(!marked[outs.top()]) {
- cnt[in] += cnt[outs.top()];
- marked[outs.top()] = true;
- }
- outs.pop();
- }
- if(outs.empty() or outs.top() != out) {
- outs.push(out);
- }
- cnt[in]++;
- cnt[out]--;
- max_people = max({max_people, cnt[in], cnt[out]});
- }
- cout << (max_people + k - 1) / k << nl;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(nullptr);
- int tests = 1;
- cin >> tests;
- for(int test = 1;test <= tests;test++) {
- run_cases();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement