結果
問題 | No.2667 Constrained Permutation |
ユーザー | 👑 Nachia |
提出日時 | 2024-03-08 21:26:00 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 4,640 bytes |
コンパイル時間 | 1,135 ms |
コンパイル使用メモリ | 106,780 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-09-29 18:57:41 |
合計ジャッジ時間 | 4,917 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#ifdef NACHIA#define _GLIBCXX_DEBUG#else#define NDEBUG#endif#include <iostream>#include <string>#include <vector>#include <algorithm>#include <utility>#include <queue>#include <array>#include <cmath>#include <atcoder/modint>namespace nachia{int Popcount(unsigned long long c) noexcept {#ifdef __GNUC__return __builtin_popcountll(c);#elsec = (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 != 0int MsbIndex(unsigned long long x) noexcept {#ifdef __GNUC__return 63 - __builtin_clzll(x);#elseusing 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 != 0int LsbIndex(unsigned long long x) noexcept {#ifdef __GNUC__return __builtin_ctzll(x);#elsereturn MsbIndex(x & -x);#endif}}namespace nachia {struct DsuFast{private:std::vector<int> 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 nachianamespace nachia {struct DecrementalPredecessorQuery{private:int n;int b;std::vector<unsigned long long> X;nachia::DsuFast Y;std::vector<int> 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<b; i++) dsuTrans[i] = i;}// remove token ivoid dec(int i){i++;int c = i/64, d = i%64;X[c] &= ~(1ull << d);if(X[c] == 0){int h = largeQ(c+1);dsuTrans[Y.merge(c, c+1)] = h;}}// minimum token left x : i <= xint queryNoLessThan(int i){if(n <= i) return n;if(i < 0) i = 0;i++;int c = i/64, d = i%64;int x = smallQ(c, d);if(x >= 0) return x-1;c = largeQ(c+1); d = 0;return smallQ(c, d)-1;}};} // namespace nachiausing 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<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;using Modint = atcoder::static_modint<998244353>;using namespace std;void testcase(){i64 N; cin >> N;vector<pair<i64,i64>> A(N);for(auto& [r,l] : A){ cin >> l >> r; l--; r--; }sort(A.begin(), A.end());i64 x = INF;rep(i,N) chmin(x, A[i].first - i);auto f = [&](i64 k) -> bool {auto dec = nachia::DecrementalPredecessorQuery(N);for(auto [r,l] : A){i64 q = dec.queryNoLessThan(l - k);if(N <= q || r < q+k) return false;dec.dec(q);}return true;};i64 ansL = x; {i64 ok = x;i64 ng = -1;while(ng + 1 < ok){i64 k = ng + (ok - ng) / 2;(f(k) ? ok : ng) = k;}ansL = ok;}i64 ansR = x-1; {i64 ok = x-1;i64 ng = INF;while(ok + 1 < ng){i64 k = ok + (ng - ok) / 2;(f(k) ? ok : ng) = k;}ansR = ok;}i64 ans = ansR - ansL + 1;cout << ans << endl;}int main(){ios::sync_with_stdio(false); cin.tie(nullptr);#ifdef NACHIAint T; cin >> T; for(int t=0; t<T; T!=++t?(cout<<'\n'),0:0)#endiftestcase();return 0;}