Skip to content

1137: 小津的摸鱼时间

题目

题目描述

在上完了一天的课之后,津津回到了宿舍,又开始不高兴了。她想要放松,想要彻底的放松,随手拿起了手机刷起了某乎。

经历了长期的摸鱼实践,小津发现了两个惊人的事实。原来某乎推送的文章是和时间密切相关的。也就是说,在 23 :00 刷到的一定是文章 A,在 23 : 10 刷到的一定是文章 B。在理论上,津津看完文章 A 之后便会有一个心情值的改变,我们定义津津看完文章 A 之后心情值的变化为 $H_A$ 。$H$ 可正可负,因为津津会刷到自己感兴趣的东西,同样也会刷到一些毫无意义的文章,这可能会使得津津更加的不开心。

当然,目前的某乎推送功能尚不完善,可能会给津津重复推送同一篇文章,这个时候津津看完这篇文章之后心情值的改变可能就没有那么大。津津经过反复的试验,终于发现,多次查看同一文章时,后一次的心情值波动总是前一次的一半(向零取整)。

假设第一次看到某篇文章能够让自己的心情值改变 $H$, 那么第二次看到该文章时心情值的改变就只有 $H/2$ (按照一般编程语言内的整数除法,向零取整,也就是 $H = sign(H) \times \lfloor \frac{|H|}{2}\rfloor$),第三次看到该文章时的心情值就是 $(H / 2) / 2$, 以此类推。

现在,小津偷看了某乎的后台算法,知道了具体每一时刻某乎会向其推送的文章 $A$,也知道每篇文章在第一次查看时会对自己的心情值产生的影响 $H$。津津想要快乐,但她也很懒,只想连续地摸鱼。

现在她需要你来为她决定摸鱼的时间段,使得她可以获得最大的快乐。津津想要尽早摸鱼,所以如果两个摸鱼方案获得的快乐相同,请告诉她开始摸鱼时间较早的那一个方案。同时津津也不想睡太晚,如果获得的快乐相同,且开始时间也相同,请告诉她结束时间也最早的方案。

方便起见,我们认为小津可以瞬间阅读完推送的文章,并产生相应的心情值波动。

她必须摸鱼,所以至少刷一篇文章。

输入格式

第一行,两个正整数 $n$ 和 $m$, $n$ 表示某乎的后台一共有 $n$ 篇文章, $m$ 表示这一天一共会出现 $m$ 次推送。

第二行,$n$ 个整数,第 $i$ 个整数表示 $H_i$,表示编号为 $i$ 的文章会在津津第一次查看时为其带来 $H_i$ 的心情值波动。

第三行到末尾,一共 $m$ 行,每行四个整数,分别是 hh, mm, ss , $A_i$,表示在 hhmmss秒这个时间点,某乎会为小津推送的文章编号为 $A_i$。保证时间点按照时间顺序排列,且不会有两个时间点重复。

输出格式

第一行,输出三个整数,hh,mm,ss。表示最佳方案中小津开始摸鱼的时间。

第二行,输出三个整数,hh,mm,ss。表示最佳方案中小津结束摸鱼的时间。

样例输入

text 4 6 -1 4 -3 4 6 0 0 1 6 1 23 2 6 2 34 3 6 13 45 4 6 20 59 3 6 28 0 4

样例输出

text 6 1 23 6 28 0

数据范围

对于所有测试点,我们保证文章第一次阅读时对心情的影响 $H \in [-16384, 16384]$ 。

对于所有测试点,显然一天的时间点最多只有 $24 \times 60 \times 60 = 86400$ ,所以推送总数也不会超过这个值。

特殊性质有:

  • A:某乎算法改进,同一文章只推送一次。
  • B:小津看淡一切,情绪波动减少, $H \in {-1, 0, 1}$。
  • C:某乎服务器崩溃,剩余文章大幅减少。
  • D:小津决定自律,她只会查看 23:00:00 ~ 23:59:59 的推送(测试数据中不会出现其他时间的推送)
数据包 文章总数 (n) 推送总数 (m) 特殊性质
1 n = 1 1 ≤ m ≤ 10 C,D
2 n = 2 1 ≤ m ≤ 86400 C
3 n = 993 1 ≤ m ≤ 360 D
4 n = 9994 1 ≤ m ≤ 3600 A,D
5 n = 99995 1 ≤ m ≤ 3600 D
6 n = 99996 1 ≤ m ≤ 86400 A
7 n = 99997 1 ≤ m ≤ 86400 A
8 n = 99998 1 ≤ m ≤ 86400 B
9 n = 99999 1 ≤ m ≤ 86400 B
10 n = 100000 1 ≤ m ≤ 86400