Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2129-109ee7b5
この記事にトラックバックする(FC2ブログユーザー)

UVa 12345 - Dynamic len(set(a[L:R])) (この記事を編集する[管理者用])

Source

ACM ICPC Regional Warmup 2011 (2011-10-29)
UVa 12345

問題概要

長さn (50000以下) の整数列 (整数は1以下1000000以下) が与えられる.
クエリがm個 (50000以下) 与えられるので,そのクエリをこなす問題.クエリは以下の二種類.
 1. 配列の1つの要素を書き換える
 2. 配列のある範囲にある数字の種類数を求める
テストケースの数は1個.

解法

タイムリミットも長いし,テストケースも1個なので,O(nm)で愚直にやっても十分通った.
出てきた数字を覚えておくときに,長さ1000000の配列を用意して,最後に登場したクエリ番号を入れておくなどすると,
最初に1回だけ初期化すれば,クエリごとに長さ1000000の配列は初期化不要.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2129-109ee7b5
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。