#252269 (C++17) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: ciel
• 提出日時: 2018-04-18 00:32:20
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,124 bytes
• コンパイル時間: 591 ms
• コンパイル使用メモリ: 64,464 KB
• 実行使用メモリ: 8,576 KB
• 最終ジャッジ日時: 2023-09-09 11:12:08
• 合計ジャッジ時間: 4,626 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 8,560 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	1 ms; 4,376 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	2 ms; 4,380 KB
testcase_12	AC	4 ms; 4,376 KB
testcase_13	AC	14 ms; 4,380 KB
testcase_14	AC	15 ms; 4,376 KB
testcase_15	AC	13 ms; 4,376 KB
testcase_16	TLE	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-

ソースコード

#include <vector>
#include <set>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef pair<long long,long long> pll;

long long checkio(const vector<pll> &v){
	long long result=0;
	long long l,r;
	set<pll> se;
	for(auto &e:v){
		l=e.first,r=e.second;
		auto right=se.lower_bound(make_pair(l,0LL)); //p.first <= right.first
		if(right!=se.begin()){
			--right;
			auto left=right;
			++right;
			if(l<=left->second+1){ // overlap with left
				l=left->first;
				r=max(r,left->second);
				result-=left->second-left->first+1;
				se.erase(left);
			}
		}
		while(right!=se.end() && right->first-1<=r){ // overlap with right
			r=max(r,right->second);
			result-=right->second-right->first+1;
			se.erase(right++);
		}
		result+=r-l+1;
		se.insert(make_pair(l,r));

		auto &x=*max_element(se.begin(),se.end(),[](const pll& a,const pll &b){
			return a.second-a.first+1 < b.second-b.first+1;
		});
		printf("%lld\n",x.second-x.first+1);
	}
	return result;
}

int main(){
	vector<pll>data;
	long long a,b;
	scanf("%lld%lld",&a,&b);
	for(;~scanf("%lld%lld",&a,&b);){
		data.emplace_back(a,b);
	}
	checkio(data);
}