結果

問題 No.674 n連勤
ユーザー seica_at_seseica_at_se
提出日時 2018-04-14 18:51:24
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 88 ms / 2,000 ms
コード長 3,083 bytes
コンパイル時間 2,338 ms
コンパイル使用メモリ 173,768 KB
実行使用メモリ 4,548 KB
最終ジャッジ日時 2023-09-09 05:26:17
合計ジャッジ時間 3,697 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 7 ms
4,376 KB
testcase_12 AC 8 ms
4,380 KB
testcase_13 AC 70 ms
4,380 KB
testcase_14 AC 73 ms
4,380 KB
testcase_15 AC 69 ms
4,376 KB
testcase_16 AC 87 ms
4,548 KB
testcase_17 AC 88 ms
4,420 KB
testcase_18 AC 79 ms
4,380 KB
testcase_19 AC 72 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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){
		if(this->size() == 0){
			(*this)[l] = r;
		//	cout << "!" << endl;
			return;
		}
		auto it = this->upper_bound(l);
		//cout << "upper " << (it->first) << ' ' << (it->second) << endl;
		if(it == this->begin() && r + AdjacentMarge< it->first){
			(*this)[l] = r;
		//	cout << "!!" << endl;
			return;
		}
		if(it != this-> end() && 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);
			r = max(r,itl->second);
		}
		while(it != this->end() && it->second <= r){
			it++;
		}
		if(it->first > r + AdjacentMarge)--it;
		if(it != this->end())r = max(r,it->second);
		//cout << "l " << (itl->first) << ' ' << (itl->second) << endl;
		//cout << "r " << (it->first) << ' ' << (it->second) << endl;
		if(it != this->end())it++;
		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;
}
0