#251588 (C++11) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: seica_at_se
• 提出日時: 2018-04-14 17:58:18
• 言語: C++11 (gcc 11.4.0)
• 結果: RE
• 実行時間: -
• コード長: 2,924 bytes
• コンパイル時間: 1,227 ms
• コンパイル使用メモリ: 153,192 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-09-09 05:22:28
• 合計ジャッジ時間: 4,037 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	AC	1 ms; 4,376 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	WA	-
testcase_07	RE	-
testcase_08	WA	-
testcase_09	AC	2 ms; 4,376 KB
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	AC	69 ms; 4,376 KB
testcase_14	AC	72 ms; 4,376 KB
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-

ソースコード

#include <bits/stdc++.h>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 1000000007
#define PI 3.14159265359

typedef long long ll;
typedef pair<ll,ll> P;

template <typename T>
class SectionManagement : public std::map<T,T> {
private:
   // if merge [l, c] and [c+1, r], set flagToMergeAdjacentSegment to true
	bool AdjacentMarge;
public:
	SectionManagement(bool flag):AdjacentMarge(flag){}
	
	void print(){
		cout << "print SectionManagement" << endl;
		for(auto it = this->begin();it != this->end();it++){
			cout << (it->first) << ' ' << (it->second) << endl;
		}
		cout << "end print" << endl;
	}
	
	//該当の区間を得る、なければend()
    typename std::map<T, T>::const_iterator get(T p) const{
        auto it = this->upper_bound(p);
        if (it == this->begin() || (--it)->second < p) return this->end();
        return it;
    }
	//挿入、被る所はひとつにまとめる。
	void insert(T l,T r){
		auto it = this->upper_bound(l);
	//	cout << "upper " << (it->first) << ' ' << (it->second) << endl;
		if(this->size() == 0 || (it == this->begin() && r + AdjacentMarge< it->first)){
			(*this)[l] = r;
	//		cout << "!!" << endl;
			return;
		}
		if(it != this->begin() && r + AdjacentMarge < it->first && l > std::prev(it)->second + AdjacentMarge){
			(*this)[l] = r;
	//		cout << "!!!" << endl;
			return;
		}
		auto itl = it;
	//	cout << "prev " << (std::prev(it)->first) << ' ' << (std::prev(it)->second) << endl;
	//	cout << std::prev(it)->second + AdjacentMarge << endl;
		if(it != this->begin() && std::prev(it)->second + AdjacentMarge >= l){
			--itl;
			l = min(l,itl->first);
		}
		while(it != this->end() && it->second <= r){
			it++;
		}
		if(it->first > r + AdjacentMarge)--it;
		r = max(r,it->second);
	//	cout << "l " << (itl->first) << ' ' << (itl->second) << endl;
	//	cout << "r " << (it->first) << ' ' << (it->second) << endl;
		this->erase(itl,++it);
		(*this)[l] = r;
	}

	//同じ区間にあるか
    bool same(T p, T q) const {
        const auto it = get(p);
        return it != this->end() && it->first <= q && q <= it->second;
	}
};

int main()
{
	SectionManagement<ll> mp(true);
	ll d,q;cin >> d >> q;
	ll ans = 0;
	REP(_,q){
		ll a,b;cin >> a >> b;
		mp.insert(a,b);
		auto it = mp.get(a);
		ans = max(ans,it->second - it->first + 1);
		cout << ans << endl;
	//	mp.print();
	}
	return 0;
}