[TIOJ] 1410. Comiket

題目連結:http://tioj.infor.org/problems/1410
裸的區間加值,查詢全部最大值問題。因為沒有奇怪的修改之類的,所以我們可以直接用個簡單的技巧,先插入兩個小標記之後再往後推過去一遍的作法做,而這題應為值域太大要先離散話,或是向我一樣懶懶的直接開個map解決他。
#include <bits/stdc++.h>
using namespace std;

map<long long,int> mp;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++){
		long long l, r; cin>>l>>r;
		mp[l]++;
		mp[r+1]--;
	}
	int cur = 0, ans = 0;
	for(auto i: mp){
		cur += i.second;
		ans = max(ans, cur);
	}
	cout<<ans<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology