#define _GLIBCXX_DEBUG #include #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<(i64)(n); i++) #define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--) const i64 INF = 1001001001001001001; const char* yn(bool x){ return x ? "Yes" : "No"; } template void chmin(A& l, const B& r){ if(r < l) l = r; } template void chmax(A& l, const B& r){ if(l < r) l = r; } using namespace std; namespace nachia{ int Popcount(unsigned long long c) noexcept { #ifdef __GNUC__ return __builtin_popcountll(c); #else c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3)); c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5)); c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17)); c = (c * (~0ull/257)) >> 56; return c; #endif } // please ensure x != 0 int MsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return 63 - __builtin_clzll(x); #else using u64 = unsigned long long; int q = (x >> 32) ? 32 : 0; auto m = x >> q; constexpr u64 hi = 0x8888'8888; constexpr u64 mi = 0x1111'1111; m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35; m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31; q += (m & 0xf) << 2; q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf; return q; #endif } // please ensure x != 0 int LsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return __builtin_ctzll(x); #else return MsbIndex(x & -x); #endif } } namespace nachia { struct DsuFast{ private: std::vector w; public: DsuFast(int n = 0) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int operator[](int u){ return leader(u); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(-w[u] < -w[v]) std::swap(u, v); w[u] += w[v]; w[v] = u; return u; } int size(int u){ return -w[leader(u)]; } bool same(int u, int v){ return leader(u) == leader(v); } }; } // namespace nachia namespace nachia { struct DecrementalPredecessorQuery{ private: int n; int b; std::vector X; nachia::DsuFast Y; std::vector dsuTrans; int smallQ(int c, int d) const noexcept { auto z = X[c] & ((~0ull) << d); return z ? c*64 + LsbIndex(z) : -1; } int largeQ(int c) noexcept { return dsuTrans[Y.leader(c)]; } public: DecrementalPredecessorQuery(int _n) : n(_n+2), b(n/64+2), X(b, ~0ull), Y(b), dsuTrans(b) { for(int i=0; i= 0) return x-1; c = largeQ(c+1); d = 0; return smallQ(c, d)-1; } }; } // namespace nachia #include namespace nachia{ template void EnsurePermutation(Iterator first, Iterator last){ int n = std::distance(first, last); std::vector vis(n, 0); for(Iterator i=first; i!=last; i++){ assert(0 <= *i); assert(*i < n); assert(vis[*i] == 0); vis[*i] = 1; } } template std::vector Permute( const std::vector& src, const std::vector& perm ){ const bool DEBUG = true; int n = src.size(); if constexpr (DEBUG){ assert(perm.size() == src.size()); EnsurePermutation(perm.begin(), perm.end()); } std::vector res; res.reserve(n); for(int i=0; i std::vector& PermuteInPlace( std::vector& src, std::vector perm ){ const bool DEBUG = true; int n = src.size(); if constexpr (DEBUG){ assert(perm.size() == src.size()); EnsurePermutation(perm.begin(), perm.end()); } for(int s=0; s BucketSortPermutation( std::vector::const_iterator first, std::vector::const_iterator last, int maxVal ){ const bool DEBUG = true; int n = last - first; if constexpr (DEBUG){ for(auto itr = first; itr != last; itr++){ assert(0 <= *itr); assert(*itr <= maxVal); } } std::vector cnt(maxVal+2); std::vector res(n); for(int i=0; i std::vector BucketSortPermutation( typename std::vector::const_iterator first, typename std::vector::const_iterator last, const Mapping& f, int maxVal ){ std::vector buf(last - first); auto bufitr = buf.begin(); for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr); return BucketSortPermutation(buf.begin(), buf.end(), maxVal); } // stable sort template std::vector BucketSort( std::vector src, const Mapping& f, int maxVal ){ return PermuteInPlace(src, BucketSortPermutation(src.begin(), src.end(), f, maxVal)); } // stable sort template std::vector BucketSortPermutation( Iter first, Iter last, const Mapping& f, int maxVal ){ std::vector buf(std::distance(first, last)); auto bufitr = buf.begin(); for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr); return BucketSortPermutation(buf.begin(), buf.end(), maxVal); } template void PermuteInPlace( Iter srcFirst, Iter srcLast, std::vector perm ){ const bool DEBUG = true; int n = std::distance(srcFirst, srcLast); if constexpr (DEBUG){ assert(perm.size() == (size_t)n); EnsurePermutation(perm.begin(), perm.end()); } for(int s=0; s void BucketSort( Iter destFirst, Iter destLast, const Mapping& f, int maxVal ){ PermuteInPlace(destFirst, destLast, BucketSortPermutation(destFirst, destLast, f, maxVal)); } } void testcase(){ int N; cin >> N; vector L(N), R(N); rep(i,N){ cin >> L[i] >> R[i]; L[i]--; R[i]--; } int ld = 0; { ld = *max_element(L.begin(), L.end()) - (N-1); rep(i,N){ L[i] -= ld; chmax(L[i], 0); } } int rd = 0; { rd = *min_element(R.begin(), R.end()); rep(i,N){ R[i] -= rd; chmin(R[i], N-1); } } int rmin = *min_element(R.begin(), R.end()); auto IL = nachia::BucketSortPermutation(L.begin(), L.end(), N-1); auto IR = nachia::BucketSortPermutation(R.begin(), R.end(), N-1); int x = -1001001001; rep(i,N) chmax(x, L[IL[i]] + ld - i); int y = 1001001001; rep(i,N) chmin(y, R[IR[i]] + rd - i); int f = true; auto dec = nachia::DecrementalPredecessorQuery(N); for(auto i : IR){ int l = L[i] + ld - x, r = R[i] + rd - x; i64 q = dec.queryNoLessThan(l); if(N <= q || r < q){ cout << "0\n"; return; } dec.dec(q); } cout << max(0, y-x+1) << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef NACHIA int T; cin >> T; for(int t=0; t