結果
問題 | No.2667 Constrained Permutation |
ユーザー | SnowBeenDiding |
提出日時 | 2024-03-08 22:39:29 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,991 bytes |
コンパイル時間 | 5,803 ms |
コンパイル使用メモリ | 326,372 KB |
実行使用メモリ | 18,292 KB |
最終ジャッジ日時 | 2024-03-08 22:39:39 |
合計ジャッジ時間 | 10,419 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,480 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
ソースコード
#include <atcoder/all> using namespace atcoder; using mint = modint998244353; const long long MOD = 998244353; // using mint = modint1000000007; // const long long MOD = 1000000007; // using mint = modint;//mint::set_mod(MOD); #include <bits/stdc++.h> #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) #define repeq(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); i++) #define repreq(i, a, b) for (ll i = (ll)(a); i >= (ll)(b); i--) #define endl '\n' // fflush(stdout); #define cYes cout << "Yes" << endl #define cNo cout << "No" << endl #define sortr(v) sort(v, greater<>()) #define pb push_back #define pob pop_back #define mp make_pair #define mt make_tuple #define FI first #define SE second #define ALL(v) (v).begin(), (v).end() #define INFLL 3000000000000000100LL #define INF 1000000100 #define PI acos(-1.0L) #define TAU (PI * 2.0L) using namespace std; typedef long long ll; typedef pair<ll, ll> Pll; typedef tuple<ll, ll, ll> Tlll; typedef vector<int> Vi; typedef vector<Vi> VVi; typedef vector<ll> Vl; typedef vector<Vl> VVl; typedef vector<VVl> VVVl; typedef vector<Tlll> VTlll; typedef vector<mint> Vm; typedef vector<Vm> VVm; typedef vector<string> Vs; typedef vector<double> Vd; typedef vector<char> Vc; typedef vector<bool> Vb; typedef vector<Pll> VPll; typedef priority_queue<ll> PQl; typedef priority_queue<ll, vector<ll>, greater<ll>> PQlr; /* inout */ ostream &operator<<(ostream &os, mint const &m) { os << m.val(); return os; } istream &operator>>(istream &is, mint &m) { long long n; is >> n, m = n; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, 0, n) { os << v[i] << " \n"[i == n - 1]; } return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, 0, n) os << v[i]; return os; } template <typename T, typename S> ostream &operator<<(ostream &os, pair<T, S> const &p) { os << p.first << ' ' << p.second; return os; } template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &ma) { for (auto &[key, val] : ma) { os << key << ':' << val << '\n'; } return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? ' ' : '\n'); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? ' ' : '\n'); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, queue<T> q) { while (q.size()) { os << q.front(); q.pop(); os << " \n"[q.empty()]; } return os; } template <typename T> ostream &operator<<(ostream &os, deque<T> dq) { while (dq.size()) { os << dq.front(); dq.pop_front(); os << " \n"[dq.empty()]; } return os; } template <typename T> ostream &operator<<(ostream &os, stack<T> st) { vector<T> v; while (st.size()) { v.push_back(st.top()); st.pop(); } reverse(ALL(v)); os << v; return os; } template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { vector<T> v; while (pq.size()) { v.push_back(pq.top()); pq.pop(); } os << v; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; } template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } /* useful */ template <typename T> int SMALLER(vector<T> &a, T x) { return lower_bound(a.begin(), a.end(), x) - a.begin(); } template <typename T> int orSMALLER(vector<T> &a, T x) { return upper_bound(a.begin(), a.end(), x) - a.begin(); } template <typename T> int BIGGER(vector<T> &a, T x) { return a.size() - orSMALLER(a, x); } template <typename T> int orBIGGER(vector<T> &a, T x) { return a.size() - SMALLER(a, x); } template <typename T> int COUNT(vector<T> &a, T x) { return upper_bound(ALL(a), x) - lower_bound(ALL(a), x); } template <typename T, typename S> bool chmax(T &a, S b) { if (a < b) { a = b; return 1; } return 0; } template <typename T, typename S> bool chmin(T &a, S b) { if (a > b) { a = b; return 1; } return 0; } template <typename T> void press(T &v) { v.erase(unique(ALL(v)), v.end()); } template <typename T> vector<int> zip(vector<T> a) { int n = a.size(); pair<T, int> p[n]; vector<int> v(n); for (int i = 0; i < n; i++) p[i] = make_pair(a[i], i); sort(p, p + n); int w = 0; for (int i = 0; i < n; i++) { if (i && p[i].first != p[i - 1].first) w++; v[p[i].second] = w; } return v; } template <typename T> vector<T> vis(vector<T> &v) { vector<T> S(v.size() + 1); rep(i, 1, S.size()) S[i] += v[i - 1] + S[i - 1]; return S; } template <typename T> T ceil_div(T a, T b) { if (b < 0) a = -a, b = -b; return (a >= 0 ? (a + b - 1) / b : a / b); } template <typename T> T floor_div(T a, T b) { if (b < 0) a = -a, b = -b; return (a >= 0 ? a / b : (a - b + 1) / b); } ll dtoll(double d, int g) { return round(d * pow(10, g)); } const double EPS = 1e-10; void init() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout.precision(12); cout << fixed; } // do {} while (next_permutation(ALL(vec))); /********************************** START **********************************/ void sol2(); int main() { init(); int q = 1; // cin >> q; while (q--) sol2(); return 0; } /********************************** SOLVE **********************************/ template <typename T> struct RangeSet { set<pair<T, T>> st; T TINF; RangeSet() { TINF = numeric_limits<T>::max() / 2; st.emplace(TINF, TINF); st.emplace(-TINF, -TINF); } // [l,r] covered? bool covered(T l, T r) { assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); return ite->first <= l and r <= ite->second; } bool covered(T x) { return covered(x, x); } // [l, r]がカバーされているなら,その区間を返す. // されていないなら[-TINF,-TINF]を返す pair<T, T> covered_by(T l, T r) { assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); if (ite->first <= l and r <= ite->second) return *ite; return make_pair(-TINF, -TINF); } pair<T, T> covered_by(T x) { return covered_by(x, x); } // insert[l,r], 増加量を返す T insert(T l, T r) { assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); if (ite->first <= l and r <= ite->second) return T(0); T sum_erased = T(0); if (ite->first <= l and l <= ite->second + 1) { l = ite->first; sum_erased += ite->second - ite->first + 1; ite = st.erase(ite); } else ite = next(ite); while (r > ite->second) { sum_erased += ite->second - ite->first + 1; ite = st.erase(ite); } if (ite->first - 1 <= r and r <= ite->second) { sum_erased += ite->second - ite->first + 1; r = ite->second; st.erase(ite); } st.emplace(l, r); return r - l + 1 - sum_erased; } T insert(T x) { return insert(x, x); } // erase [l,r], 減少量を返す T erase(T l, T r) { assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); if (ite->first <= l and r <= ite->second) { // 完全に1つの区間に包含されている if (ite->first < l) st.emplace(ite->first, l - 1); if (r < ite->second) st.emplace(r + 1, ite->second); st.erase(ite); return r - l + 1; } T ret = T(0); if (ite->first <= l and l <= ite->second) { ret += ite->second - l + 1; // 消えた if (ite->first < l) st.emplace(ite->first, l - 1); ite = st.erase(ite); // 次へ } else ite = next(ite); while (ite->second <= r) { ret += ite->second - ite->first + 1; ite = st.erase(ite); } // 右端が区間の間にあるか if (ite->first <= r and r <= ite->second) { ret += r - ite->first + 1; if (r < ite->second) st.emplace(r + 1, ite->second); st.erase(ite); } return ret; } T erase(T x) { return erase(x, x); } // number of range int size() { return (int)st.size() - 2; } // mex [x,~) int mex(T x = 0) { auto ite = prev(st.lower_bound({x + 1, x + 1})); if (ite->first <= x and x <= ite->second) return ite->second + 1; else return x; } // mexr (~ , x] int mexr(T x = 0) { auto ite = prev(st.lower_bound({x + 1, x + 1})); if (ite->first <= x and x <= ite->second) return ite->first - 1; else return x; } void output() { cout << "RangeSet : "; for (auto &p : st) { if (p.first == -TINF or p.second == TINF) continue; cout << "[" << p.first << ", " << p.second << "] "; } cout << "\n"; } }; ll sol(int n, vector<ll> l, vector<ll> r) { auto check = [&](ll mid) { // ([...,1,1,1,0,0,0,...]) vector<pair<ll, ll>> v; rep(i, 0, n) v.pb({r[i] + mid, l[i] + mid}); sort(ALL(v)); RangeSet<ll> rs; vector<ll> ad; rep(i, 0, n) { ll mx = rs.mex(v[i].SE); rs.insert(mx); ad.push_back(mx); } sort(ALL(ad)); rep(i, 0, n) if (ad[i] > i) return false; return true; }; auto binary = [&]() { // ll ll L = -2e9, R = +2e9; // 解[L,R) 探索範囲(L,R) ll mid = L + (R - L) / 2; while (R - L > 1) { if (check(mid)) L = mid; else R = mid; mid = L + (R - L) / 2; } return L; // L-true R-false }; ll ret = binary(); return ret; } void sol2() { int n; cin >> n; vector<ll> l(n), r(n); rep(i, 0, n) cin >> l[i] >> r[i], l[i]--, r[i]--; ll li = sol(n, l, r); ll maxx = 1e9; // rep(i, 0, n) chmax(maxx, r[i]); rep(i, 0, n) { // l[i] = maxx - l[i]; // r[i] = maxx - r[i]; swap(l[i], r[i]); } ll ri = sol(n, l, r); cerr << li << " " << ri << endl; ll ans = li - ri; cout << ans + 1 << endl; }