TopCoder SRM 767 : Div1 Easy ArpaAsDevotee

今回は不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=15617

問題

オンラインゲームにおいて、友人がオンラインだったりオフラインだったりする。
N回自分が状況を確認した際、確認した時刻A[i]と、その時点での最終オンライン時刻B[i]の情報が与えられる。

まず、その情報に不整合が無いか確認せよ。
不整合が無い場合、加えてクエリとして時刻が与えられる。
その際の友人のオンライン状況を答えよ。

解法

まず不整合をチェックする。

• A[i]=A[j]なのにB[i]!=B[j]なのはおかしい。
• B[j]≦A[i]＜A[j]の場合、B[i]!=B[j]なのはおかしい。

あとはA[i]とB[i]の値から、時刻B[i]はオフライン確定で、(B[i]+1)～A[i]はオフライン確定であることがわかる。
ここから各クエリに回答していけばよい。

int S[86400];
class ArpaAsDevotee {
	public:
	vector <string> solve(int n, int q, vector <int> a, vector <int> lastSeen, vector <int> t) {
		int i,x,y;
		ZERO(S);
		FOR(x,n) {
			if(a[x]<lastSeen[x]) return {};
			FOR(y,n) if(x!=y) {
				if(a[x]==a[y] && lastSeen[x]!=lastSeen[y]) return {};
				if(a[x]<a[y]) {
					if(lastSeen[y]<=a[x] && lastSeen[x]!=lastSeen[y]) return {};
					
				}
			}
			S[lastSeen[x]]=1;
			for(i=lastSeen[x]+1;i<=a[x];i++) S[i]=2;
		}
		
		vector<string> V;
		FORR(s,t) {
			if(S[s]==1) V.push_back("Yes");
			if(S[s]==2) V.push_back("No");
			if(S[s]==0) V.push_back("Not Sure");
		}
		
		return V;
		
		
	}
}

まとめ

最近参加者が少なくてさみしいね。