yukicoder : No.945 YKC饅頭

簡単目の★3。
https://yukicoder.me/problems/no/945

問題

N個の皿が並んでいる。
i番目の処理では、区間[L,R]の間の空き皿に指定した模様の饅頭を置く。
最終的に各皿におかれた饅頭の模様毎の個数を答えよ。

解法

色々な解法がある。

• SegTreeで更新時刻の最小値を取る
• 端から走査していき、各皿の対象クエリのうち最古のものを取る
• 未処理の皿の番号をsetで持っておき、各クエリで範囲内の未処理の皿のみ処理していく。

以下の解法は2番目。

int N,M;
vector<pair<int,char>> add[202020];
vector<pair<int,char>> del[202020];

int cnt[256];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>s;
		add[x].push_back({i,s[0]});
		del[y+1].push_back({i,s[0]});
	}
	
	set<pair<int,int>> S;
	S.insert({505050,'a'});
	for(i=1;i<=N;i++) {
		FORR(a,add[i]) S.insert(a);
		FORR(a,del[i]) S.erase(a);
		cnt[S.begin()->second]++;
	}
	cout<<cnt['Y']<<" "<<cnt['K']<<" "<<cnt['C']<<endl;
}

まとめ

出遅れたなぁ。