結果
問題 |
No.674 n連勤
|
ユーザー |
![]() |
提出日時 | 2025-01-20 11:25:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 6,492 bytes |
コンパイル時間 | 5,905 ms |
コンパイル使用メモリ | 332,824 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-20 11:25:47 |
合計ジャッジ時間 | 7,324 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> std::istream &operator>>(std::istream &is, atcoder::modint &v) { long long value; is >> value; v = value; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint &v) { os << v.val(); return os; } std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint998244353 &v) { long long x; is >> x; v = x; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &v) { long long x; is >> x; v = x; return is; } #endif using namespace std; using ll = long long; using pll = pair<ll, ll>; #define newl '\n'; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--) #define all(x) begin(x), end(x) #define SZ(x) ll(x.size()) #define eb emplace_back #define pb push_back #define TT template <typename T> TT using vec = vector<T>; TT using vvec = vec<vec<T>>; TT using vvvec = vec<vvec<T>>; TT using minheap = priority_queue<T, vector<T>, greater<T>>; TT using maxheap = priority_queue<T>; TT bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; } TT bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; } TT bool rng(T l, T x, T r) { return l <= x && x < r; } TT T flr(T a, T b) { if (b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a + 1) / b - 1; } TT T cil(T a, T b) { if (b < 0) a = -a, b = -b; return a > 0 ? (a - 1) / b + 1 : a / b; } TT T sqr(T x) { return x * x; } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << p.first << " " << p.second; return os; } TT ostream &operator<<(ostream &os, const vec<T> &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template <typename T, ll n> ostream &operator<<(ostream &os, const array<T, n> &v) { for (size_t i = 0; i < n; i++) { os << v[i] << (i + 1 != n ? " " : ""); } return os; } template <typename T> ostream &operator<<(ostream &os, const vvec<T> &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? "\n" : ""); } return os; } TT istream &operator>>(istream &is, vec<T> &v) { for (size_t i = 0; i < v.size(); i++) { is >> v[i]; } return is; } #if __has_include(<debug/debug.hpp>) #include <debug/debug.hpp> #else #define dbg(...) true #define DBG(...) true #define OUT(...) true #endif template <typename T, typename F> T max_right(T l, T max_r_plus_one, F pred) { assert(l < max_r_plus_one); if (!pred(l)) return l; while (max_r_plus_one > l + 1) { T mid = ((l ^ max_r_plus_one) >> 1) + (l & max_r_plus_one); (pred(mid) ? l : max_r_plus_one) = mid; } return max_r_plus_one; }; template <typename T, typename F> T min_left(T min_l, T r, F pred) { assert(min_l < r); if (pred(min_l)) return min_l; while (r > min_l + 1) { T mid = ((min_l ^ r) >> 1) + (min_l & r); (pred(mid) ? r : min_l) = mid; } return r; } /* @brief 抽象化二分探索 @docs doc/bisect.md */ template <typename T, bool merge_adju> struct rangeset : public std::map<T, T> { rangeset() {} auto get(T p) const { auto it = (*this).upper_bound(p); if (it == (*this).begin() || (--it)->second <= p) return (*this).end(); return it; } //[l, r) pair<T, T> insert(T l, T r) { if (l == r) return make_pair(l, r); assert(l <= r); auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r + merge_adju); if (itl != (*this).begin() && (--itl)->second + merge_adju <= l) { ++itl; } if (itl != itr) { if (itl->first < l) l = itl->first; if (prev(itr)->second > r) r = prev(itr)->second; map<T, T>::erase(itl, itr); } (*this)[l] = r; return make_pair(l, r); } pair<T, T> insert(T p) { insert(p, p + 1); } //[l, r) void erase(T l, T r) { if (l == r) return; assert(l <= r); auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r); if (itl != (*this).begin() && (--itl)->second <= l) { ++itl; } if (itl == itr) return; T tl = l, tr = r; if (itl->first < l) tl = itl->first; if (prev(itr)->second > r) tr = prev(itr)->second; map<T, T>::erase(itl, itr); if (tl < l) (*this)[tl] = l; if (tr > r) (*this)[r] = tr; } void erase(T p) { erase(p, p + 1); } // pを含む区間があるか bool contains(T p) const { return get(p) != (*this).end(); } //[l, r)のうち1要素でも含まれているか bool contains(T l, T r) const { auto itl = (*this).upper_bound(l), itr = (*this).lower_bound(r); if (itl != (*this).begin() && (--itl)->second <= l) { ++itl; } if (itl == itr) return false; else return true; } // aとbを共に含む区間があるか bool same(T a, T b) const { if (a > b) swap(a, b); auto it = get(a); if (it == (*this).end()) return false; return b < it->second; } T mex(T x = 0) const { auto it = get(x); if (it == (*this).end()) return x; else return it->second; } template <typename TYPE, bool ME> friend ostream &operator<<(ostream &os, rangeset<TYPE, ME> const &rhs) { for (auto [l, r] : rhs) os << "[" << l << ", " << r << ")"; return os; } }; int main() { ll d, q; cin >> d >> q; rangeset<ll, true> rs; ll m = 0; while(q--) { ll a, b; cin >> a >> b; b++; auto [l, r] = rs.insert(a, b); chmax(m, r - l); cout << m << newl; } } /* 同じ議論を繰り返さない do smth instead of nothing and stay organized WRITE STUFF DOWN DON'T GET STUCK ON ONE APPROACH */