Problem:


Score : 100 points

Problem Statement

Takahashi recorded his daily life for the last few days as a integer sequence of length 2N, as follows:

a_1, b_1, a_2, b_2, ... , a_N, b_N

This means that, starting from a certain time T, he was:

sleeping for exactly a_1 seconds

then awake for exactly b_1 seconds

then sleeping for exactly a_2 seconds

:

then sleeping for exactly a_N seconds

then awake for exactly b_N seconds

In this record, he waked up N times.

Takahashi is wondering how many times he waked up early during the recorded period.

Here, he is said to wake up early if he wakes up between 4:00 AM and 7:00 AM, inclusive.

If he wakes up more than once during this period, each of these awakenings is counted as waking up early.

Unfortunately, he forgot the time T.

Find the maximum possible number of times he waked up early during the recorded period.

For your information, a day consists of 86400 seconds, and the length of the period between 4:00 AM and 7:00 AM is 10800 seconds.

Constraints

1 \leq N \leq 10^5

1 \leq a_i, b_i \leq 10^5

a_i and b_i are integers.

Input

The input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N

Output

Print the maximum possible number of times he waked up early during the recorded period.

Sample Input 1

3
28800 57600
28800 57600
57600 28800

Sample Output 1

2

Sample Input 2

10
28800 57600
4800 9600
6000 1200
600 600
300 600
5400 600
6000 5760
6760 2880
6000 12000
9000 600

Sample Output 2

5



Sample input:
3
28800 57600
28800 57600
57600 28800


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input = sys.stdin.readline

def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist
    
oneday = 86400 
time = [ 0 for i in range(oneday) ]
n = int(input())
t = 0
for i in range(n):
    a, b = [ int(v) for v in input().split() ]
    t = (t+a) % oneday
    time[t] += 1
    t = (t+b) % oneday

time = time * 2
timesum = cumsum(time)

ans_list = []
for i in range(oneday*2-20000):
    ans_list.append(timesum[i+10800] - timesum[i])
print(max(ans_list))

Submission status: Wrong Answer

Solution code:
n = int(input())
x,num = [],0
for i in range(n):
	a,b = (int(j) for j in input().split())
	x.append((num+a)%86400)
	num = (num+a+b)%86400
x,ans = sorted(x),0
from bisect import bisect
for i in range(n): ans = max(ans,bisect(x,x[i]+10800)-i)
print(ans)

Submission status: Wrong Answer

Solution code:
H=10800
D=H*8
d=[0]*D
c=0
for i in range(input()):a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i]for i in r)

Submission status: Wrong Answer

Solution code:
N = input()
MOD = 86400
A = [0 for _ in xrange(86400)]
T = 0
for _ in xrange(N):
    a, b = map(int, raw_input().split())
    T = (T+a)%MOD
    A[T] += 1
    T = (T+b)%MOD
A.insert(0, 0)
A *= 2
for i in xrange(1, MOD*2):
    A[i] += A[i-1]
 
 
ans = 0
for i in xrange(MOD+10):
    ans = max(ans, A[i+10801]-A[i])
print ans

Submission status: Wrong Answer

Solution code:
N = input()
MOD = 86400
A = [0 for _ in xrange(86400)]
T = 0
for _ in xrange(N):
    a, b = map(int, raw_input().split())
    T = (T+a)%MOD
    A[T] += 1
    T = (T+b)%MOD
A.insert(0, 0)
A *= 2
for i in xrange(1, MOD*2):
    A[i] += A[i-1]


ans = 0
for i in xrange(MOD+10):
    ans = max(ans, A[i+10802]-A[i])
print ans

Submission status: Time Limit Exceeded

Solution code:
H=10800
D=H*8
d=[0]*D
c=0
exec("a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b;"*input())
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i-1]for i in r)

Submission status: Time Limit Exceeded

Solution code:
H=10800
D=H*8
d=[0]*D
c=0
exec("a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b;"*input())
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i]for i in r)

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline

def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist
    
oneday = 86400 
time = [ 0 for i in range(oneday) ]
n = int(input())
t = 0
for i in range(n):
    a, b = [ int(v) for v in input().split() ]
    t = (t+a) % oneday
    time[t] += 1
    t = (t+b) % oneday

time = time * 2
timesum = cumsum(time)

ans_list = []
for i in range(oneday*2-20000):
    ans_list.append(timesum[i+10801] - timesum[i])
print(max(ans_list))

Submission status: Accepted

Solution code:
mod = 3600 * 24
wakeup = [0] * (mod + 11000)
n = int(input())
now = 0
for i in range(n):
    a, b = [int(item) for item in input().split()]
    now += a
    now %= mod
    wakeup[now] += 1
    wakeup[now + 10801] -= 1
    now += b

for i in range(1, mod + 11000):
    wakeup[i] += wakeup[i-1]
    if i != i%mod:
        wakeup[i%mod] += wakeup[i]

print(max(wakeup))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
AB = np.array(sys.stdin.read().split(), dtype=np.int64)

T = AB.cumsum()[::2] % 86400

# 10801個の連番の集計結果の最大値

T_cnt = np.bincount(T, minlength=86400)

T_cnt = np.concatenate([T_cnt]*3)

arr = T_cnt.cumsum()
answer = (arr[10801:] - arr[:-10801]).max()
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
x,num = [],0
for i in range(n):
	a,b = (int(j) for j in input().split())
	x.append((num+a)%86400)
	num = (num+a+b)%86400
x,ans = sorted(x),0
from bisect import bisect
for i in range(n):
	ans = max(ans,bisect(x,x[i]+10800)-i)
	if x[i]<=10800: x.append(x[i]+86400)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = 86400
W = 10801
mem = [0 for i in range(T)]
time = 0
for i in range(N):
    a,b = map(int,input().split())
    time += a
    mem[time % T] += 1
    time += b

mem += mem
cums = [0]
for t in mem:
    cums.append(cums[-1] + t)

ans = 0
for t in range(T):
    ans = max(ans, cums[t+W] - cums[t])
print(ans)

Submission status: Accepted

Solution code:
n=int(raw_input())
day=86400
time=10800
cur=0
cnt=[0]*(day*2+1)
for i in xrange(n):
    a,b=map(int,raw_input().split())
    cur=(cur+a)%day
    cnt[cur]+=1
    cnt[cur+day]+=1
    cur=(cur+b)%day
for i in xrange(day*2):
    cnt[i+1]+=cnt[i]
ans=0
for i in xrange(day):
    if i==0:
        ans=max(ans,cnt[i+time])
    else:
        ans=max(ans,cnt[i+time]-cnt[i-1])
print ans

Submission status: Accepted

Solution code:
DAY = 86400
HOURS = 10801
N = input()
okita = [0 for _ in xrange(DAY)]
t = 0
for _ in xrange(N):
    a, b = map(int, raw_input().split())
    t = (t+a)%DAY
    okita[t] += 1
    t = (t+b)%DAY
okita *= 2
okita.insert(0, 0)
for i in xrange(1, DAY*2):
    okita[i] += okita[i-1]
 
 
ans = 0
for i in xrange(DAY+10):
    ans = max(ans, okita[i+HOURS]-okita[i])
print ans

Submission status: Accepted

Solution code:
H=10800
D=H*8
d=[0]*D
c=0
for i in[0]*input():a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i-1]for i in r)