#P7085. [2019年安徽集训]B

    ID: 6916 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>计算几何凸包动态规划贪心算法基础分治斜率优化模拟CF2400

[2019年安徽集训]B

B

题目描述

有 nn 个人分仓鼠吃,每个人分到的仓鼠有两个属性:大小 ss、美味值 tt。

对于 i<ji<j,其后连续一段人 i+1,…,ji+1,\ldots,j 分到的仓鼠的平均美味值定义为

∑k=i+1jtk∑k=i+1jsk。\frac{\sum_{k=i+1}^{j}t_k}{\sum_{k=i+1}^{j}s_k}。

这是总美味值除以总大小,不是对各个 tkt_k 作算术平均。第 ii 个人心中有两个值 li,ril_i,r_i;若上述平均值小于 lil_i 或大于 rir_i,他就看第 jj 个人不顺眼。等于端点时属于范围内。

只考虑 j>ij>i 的对象。

现在你知道了所有这些信息,并想知道哪些人会看别人不顺眼,以及哪些人会被别人看不顺眼。

由于答案可能很大,你只需要分别输出:

  • 哪些人会看别人不顺眼;
  • 哪些人会被别人看不顺眼。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,每行包含四个整数 si,ti,li,ris_i,t_i,l_i,r_i。

输出格式

输出两行 01 串,每行长度均为 nn。

  • 第一行的第 ii 个字符表示第 ii 个人是否会看别人不顺眼;
  • 第二行的第 ii 个字符表示第 ii 个人是否会被别人看不顺眼。

其中,字符 1 表示“是”,字符 0 表示“否”。

样例 1

输入

3
4 24 5 7
16 128 4 12
16 64 0 8

输出

100
010

样例 2

输入

5
2 15 7 8
16 128 4 12
16 64 0 8
20 160 3 13
20 160 3 13

输出

10000
00110

数据范围

对于 100%100\% 的数据:

$$n\le 100000, \qquad t_i\le 10^8, \qquad s_i,l_i,r_i\le 10^4.$$
测试点编号 分数 nn
1 10 2020
2 100100
3 20 10001000
4 60 100000100000
两行全部正确可得满分;只答对第一行为该测试点的 40%40\%,只答对第二行为 50%50\%。两行均须为长度 nn 的合法 01 串。