CODE FESTIVAL 2016 Relay : H - 早起き / Early Bird

こっちの方がGより楽？
http://cf16-relay-open.contest.atcoder.jp/tasks/relay_h

問題

高橋君はA[0]秒寝て、B[0]秒起きて、A[1]秒寝て、B[1]秒起きて、…、A[N-1]秒寝て、B[N-1]秒起きる、という行動を行った。
最初に行動を起こしたのは何時何分かわからないが、午前4～7時の間に起きたことは最大何回あるか求めよ。

解法

まず開始時間を0秒と仮定し、mod 86400で起きた時間を求め数える。
あとは累積和やBITによる区間和を高速に求められるようにしておけば、開始時間を86400通りずらしながら、開始時刻から3600*3+1秒の範囲にある起きた回数を数えることができる。

int N;
int num[505050];
int S[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int cur=0;
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		cur+=x;
		cur%=86400;
		num[cur]++;
		cur+=y;
		cur%=86400;
	}
	FOR(i,86400*3) {
		S[i+1]=S[i]+num[i];
		num[i+86400]=num[i];
	}
	int ma=0;
	FOR(i,86400*2) ma=max(ma,S[i+3600*3+1]-S[i]);
	cout<<ma<<endl;
	
}

まとめ

午前４時だとCodeforcesの採点終わらないけどね…。