結果

問題 No.674 n連勤
ユーザー nok0nok0
提出日時 2021-02-14 01:57:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 3,563 bytes
コンパイル時間 1,591 ms
コンパイル使用メモリ 82,600 KB
最終ジャッジ日時 2025-01-18 20:16:10
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:144:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  144 |         scanf("%lld%d", &d, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:147:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  147 |                 scanf("%lld%lld", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cassert>
#include <iostream>
#include <limits>
#include <set>
#include <vector>
template <class T>
struct RangeSet {
private:
const T TINF = std::numeric_limits<T>::max() / 2;
std::set<std::pair<T, T>> st;
public:
RangeSet() {
st.emplace(-TINF, -TINF + 1);
st.emplace(TINF, TINF + 1);
}
//[l, r) is covered?
bool covered(const T l, const T r) {
assert(l < r);
auto itr = prev(st.lower_bound({l + 1, -TINF}));
return itr->first <= l and r <= itr->second;
}
//[x, x + 1) is covered?
bool covered(const T x) { return covered(x, x + 1); }
//return section which covers[l, r)
//if not exists, return[-TINF, -TINF)
std::pair<T, T> covered_by(const T l, const T r) {
assert(l < r);
auto itr = prev(st.lower_bound({l + 1, -TINF}));
if(itr->first <= l and r <= itr->second) return *itr;
return {-TINF, -TINF};
}
//return section which covers[x, x + 1)
//if not exists, return[-TINF, -TINF)
std::pair<T, T> covered_by(const T x) { return covered_by(x, x + 1); }
//insert[l, r), and return increment
T insert(T l, T r) {
if(l >= r) return 0;
auto itr = prev(st.lower_bound({l + 1, -TINF}));
if(itr->first <= l and r <= itr->second) return T(0);
T sum_erased = T(0);
if(itr->first <= l and l <= itr->second) {
l = itr->first;
sum_erased += itr->second - itr->first;
itr = st.erase(itr);
} else
itr = next(itr);
while(r > itr->second) {
sum_erased += itr->second - itr->first;
itr = st.erase(itr);
}
if(itr->first <= r) {
sum_erased += itr->second - itr->first;
r = itr->second;
st.erase(itr);
}
st.emplace(l, r);
return r - l - sum_erased;
}
//insert[x, x + 1), and return increment
T insert(const T x) { return insert(x, x + 1); }
// erase [l, r), and return decrement
T erase(const T l, const T r) {
assert(l < r);
auto itr = prev(st.lower_bound({l + 1, -TINF}));
if(itr->first <= l and r <= itr->second) {
if(itr->first < l) st.emplace(itr->first, l);
if(r < itr->second) st.emplace(r, itr->second);
st.erase(itr);
return r - l;
}
T ret = T(0);
if(itr->first <= l and l < itr->second) {
ret += itr->second - l;
if(itr->first < l) st.emplace(itr->first, l);
itr = st.erase(itr);
} else
itr = next(itr);
while(itr->second <= r) {
ret += itr->second - itr->first;
itr = st.erase(itr);
}
if(itr->first < r) {
ret += r - itr->first;
st.emplace(r, itr->second);
st.erase(itr);
}
return ret;
}
// erase [x, x + 1), and return decrement
T erase(const T x) { return erase(x, x + 1); }
int size() { return (int)st.size() - 2; }
int mex(const T x = 0) {
auto itr = prev(st.lower_bound({x + 1, -TINF}));
if(itr->first <= x and x < itr->second)
return itr->second;
else
return x;
}
T sum_all() const {
T res = 0;
for(auto &p : st) {
if(std::abs(p.first) == TINF) continue;
res += p.second - p.first;
}
return res;
}
std::set<std::pair<T, T>> get() const {
std::set<std::pair<T, T>> res;
for(auto &p : st) {
if(std::abs(p.first) == TINF) continue;
res.emplace(p.first, p.second);
}
return res;
}
void dump() const {
std::cout << "Rangeset:";
for(auto &p : st) {
if(std::abs(p.first) == TINF) continue;
std::cout << "[" << p.first << "," << p.second << "),";
}
std::cout << '\n';
}
};
long long a, b, d, res;
int q;
int main() {
scanf("%lld%d", &d, &q);
RangeSet<long long> st;
while(q--) {
scanf("%lld%lld", &a, &b);
st.insert(a, b + 1);
auto [l, r] = st.covered_by(a);
res = std::max(res, r - l);
printf("%lld\n", res);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0