#line 1 "b.cpp" // {{{1 extern "C" int __lsan_is_turned_off() { return 1; } #include using namespace std; #include using namespace tr2; #include #define ll long long #define inf 0x3f3f3f3f #define infl 0x3f3f3f3f3f3f3f3fll #line 15 "b.cpp" #ifdef DEBUG #define dprintf(args...) fprintf(stderr,args) #endif #ifndef DEBUG #define dprintf(args...) 69 #endif #define all(x) (x).begin(), (x).end() struct cintype { template operator T() { T x; cin>>x; return x; } }; // 1}}} #line 2 "/mnt/c/Users/jayja/Documents/dev/comp/lib/ds/fenwick.hpp" #line 4 "/mnt/c/Users/jayja/Documents/dev/comp/lib/ds/fenwick.hpp" #line 3 "/mnt/c/Users/jayja/Documents/dev/comp/lib/hash.hpp" using namespace std; template static unsigned long long splitmix64(T x) { // http://xorshift.di.unimi.it/splitmix64.c unsigned long long y = hash{}(x); y += 0x9e3779b97f4a7c15; y = (y ^ (y >> 30)) * 0xbf58476d1ce4e5b9; y = (y ^ (y >> 27)) * 0x94d049bb133111eb; return y ^ (y >> 31); } template struct splitmix { unsigned long long operator()(unsigned long long x) const { static const unsigned long long FIXED_RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; unsigned long long hash_combine(unsigned long long a, unsigned long long b) { a ^= b + 0x517cc1b727220a95 + (a << 6) + (a >> 2); return a; } template struct pair_hash { unsigned long long operator() (const pair& p) const { return splitmix{}(p.first) * 69 + splitmix{}(p.second); } }; #line 6 "/mnt/c/Users/jayja/Documents/dev/comp/lib/ds/fenwick.hpp" struct ft_add { template T operator()(T a, T b) const { return a + b; } }; struct ft_min { template T operator()(T a, T b) const { return min(a, b); } }; struct ft_max { template T operator()(T a, T b) const { return max(a, b); } }; template struct fenwick // oper should be: associative, commutative, has identity { int n; std::vector t; T id; fenwick(int n, T id) : n(n), t(n, id), id(id) {} fenwick(int n) : fenwick(n, {}) {} fenwick() : fenwick(0) {} void resize(int n) { // UB if tree is nonzero this->n=n; t.resize(n); } void update(int i, T x) { for(; i> struct sparse_fenwick // oper should be: associative, commutative, has identity { int n; __gnu_pbds::gp_hash_table> t; sparse_fenwick(int n) : n(n) {} sparse_fenwick() : sparse_fenwick(0) {} void resize(int n) { // UB if tree is nonzero this->n=n; } void update(int i, T x) { for(; i ft(1e9+7); vector> pts(n); for(auto&[x,y]:pts)x=in,y=in, ft.update(x,1),ft.update(y,-1); int mx=0; for(auto [x,y] : pts) { mx=max({mx,ft.query(x),ft.query(y),ft.query(y-1)}); } printf("%d\n",mx-1); }