結果
問題 | No.674 n連勤 |
ユーザー | KowerKoint2010 |
提出日時 | 2023-01-07 10:13:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 6,951 bytes |
コンパイル時間 | 2,346 ms |
コンパイル使用メモリ | 211,904 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-05-08 07:27:22 |
合計ジャッジ時間 | 4,087 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 7 ms
6,944 KB |
testcase_12 | AC | 7 ms
6,940 KB |
testcase_13 | AC | 74 ms
6,948 KB |
testcase_14 | AC | 76 ms
6,940 KB |
testcase_15 | AC | 72 ms
6,940 KB |
testcase_16 | AC | 85 ms
6,940 KB |
testcase_17 | AC | 85 ms
6,944 KB |
testcase_18 | AC | 74 ms
6,940 KB |
testcase_19 | AC | 74 ms
6,940 KB |
ソースコード
#line 1 "test/yukicoder-674.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/674" #line 2 "stl-expansion.hpp" #include <bits/stdc++.h> template <typename T1, typename T2> std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) { is >> p.first >> p.second; return is; } template <typename T, size_t N> std::istream& operator>>(std::istream& is, std::array<T, N>& a) { for (size_t i = 0; i < N; ++i) { is >> a[i]; } return is; } template <typename T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& e : v) is >> e; return is; } template <typename T1, typename T2> std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) { os << p.first << " " << p.second; return os; } template <typename T, size_t N> std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) { for (size_t i = 0; i < N; ++i) { os << a[i] << (i + 1 == a.size() ? "" : " "); } return os; } template <typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { for (size_t i = 0; i < v.size(); ++i) { os << v[i] << (i + 1 == v.size() ? "" : " "); } return os; } #line 3 "base.hpp" using namespace std; #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define END(...) { print(__VA_ARGS__); return; } using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>; using ll = long long; using VL = vector<ll>; using VVL = vector<VL>; using VVVL = vector<VVL>; using ull = unsigned long long; using VUL = vector<ull>; using VVUL = vector<VUL>; using VVVUL = vector<VVUL>; using VD = vector<double>; using VVD = vector<VD>; using VVVD = vector<VVD>; using VS = vector<string>; using VVS = vector<VS>; using VVVS = vector<VVS>; using VC = vector<char>; using VVC = vector<VC>; using VVVC = vector<VVC>; using P = pair<int, int>; using VP = vector<P>; using VVP = vector<VP>; using VVVP = vector<VVP>; using LP = pair<ll, ll>; using VLP = vector<LP>; using VVLP = vector<VLP>; using VVVLP = vector<VVLP>; template <typename T> using PQ = priority_queue<T>; template <typename T> using GPQ = priority_queue<T, vector<T>, greater<T>>; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; void print() { cout << '\n'; } template<typename T> void print(const T &t) { cout << t << '\n'; } template<typename Head, typename... Tail> void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } #ifdef DEBUG void dbg() { cerr << '\n'; } template<typename T> void dbg(const T &t) { cerr << t << '\n'; } template<typename Head, typename... Tail> void dbg(const Head &head, const Tail &... tail) { cerr << head << ' '; dbg(tail...); } #else template<typename... Args> void dbg(const Args &... args) {} #endif template<typename T> vector<vector<T>> split(typename vector<T>::const_iterator begin, typename vector<T>::const_iterator end, T val) { vector<vector<T>> res; vector<T> cur; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(*it); } res.push_back(cur); return res; } vector<string> split(typename string::const_iterator begin, typename string::const_iterator end, char val) { vector<string> res; string cur = ""; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(*it); } res.push_back(cur); return res; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template <typename T> pair<VI, vector<T>> compress(const vector<T> &a) { int n = a.size(); vector<T> x; REP(i, n) x.push_back(a[i]); sort(ALL(x)); x.erase(unique(ALL(x)), x.end()); VI res(n); REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin(); return make_pair(res, x); } template <typename It> auto rle(It begin, It end) { vector<pair<typename It::value_type, int>> res; if(begin == end) return res; auto pre = *begin; int num = 1; for(auto it = begin + 1; it != end; it++) { if(pre != *it) { res.emplace_back(pre, num); pre = *it; num = 1; } else num++; } res.emplace_back(pre, num); return res; } template <typename It> vector<pair<typename It::value_type, int>> rle_sort(It begin, It end) { vector<typename It::value_type> cloned(begin, end); sort(ALL(cloned)); auto e = rle(ALL(cloned)); sort(ALL(e), [](const auto& l, const auto& r) { return l.second < r.second; }); return e; } template <typename T> pair<vector<T>, vector<T>> factorial(int n) { vector<T> res(n+1), rev(n+1); res[0] = 1; REP(i, n) res[i+1] = res[i] * (i+1); rev[n] = 1 / res[n]; for(int i = n; i > 0; i--) { rev[i-1] = rev[i] * i; } return make_pair(res, rev); } #line 3 "segtree/segment-set.hpp" template <typename T, T neighbor=1> struct SegmentSet { map<T, T> segments; using It = typename map<T, T>::iterator; It get(T x) const { auto it = segments.upper_bound(x); if (it == segments.begin()) return segments.end(); return prev(it); } bool contains(T x) const { return get(x) != segments.end(); } It insert(T l, T r) { auto it = segments.upper_bound(l); if(it != segments.begin() && prev(it)->second + neighbor >= l) { it = prev(it); l = it->first; } while(it != segments.end() && it->first <= r + neighbor) { r = max(r, it->second); it = segments.erase(it); } return segments.emplace_hint(it, l, r); } void erase(T l, T r) { auto it = segments.upper_bound(l); if(it != segments.begin() && prev(it)->second + neighbor > l) { it = prev(it); } while(it != segments.end() && it->first < r + neighbor) { T nl = it->first, nr = it->second; if(nl + neighbor < l) { segments.emplace(nl, l - neighbor); } if(r + neighbor < nr) { segments.emplace(r + neighbor, nr); } it = segments.erase(it); } } }; #line 3 "test/yukicoder-674.test.cpp" int main() { ll d; int q; cin >> d >> q; SegmentSet<ll> seg; ll ans = 0; while(q--) { ll a, b; cin >> a >> b; auto it = seg.insert(a, b); chmax(ans, it->second - it->first + 1); print(ans); } }