塔子哥是一名监考机器人,能够同时监控多个考场。每个考场有不同的考试开始时间和结束时间。监控一个考场的费用是每分钟 3金币;监控两个或以上的考场时,费用是每分钟 4金币;如果没有监控任务,则每分钟消耗 1金币。要求计算塔子哥在一天的监考任务中能够获得多少金币。
知识点学习:Oi-Wiki 前缀和&差分
题目意思本质为:一维正半轴上给n条线段。每个整点i有一个值vi,大小根据i点覆盖的线段个数coveri 来定.
coveri=0,vi=1
小红是一个强大严厉的监考机器人,有他监考的考场总能抓到很多不不听话的学生,小红”手眼通天“,能够同时仔细的观察很多考场,每个学生的一举一动他都能尽收眼底。
很多学校都想使用小红监督考试,而小红的使用成本也非常昂贵,当只监督一个考场时,每监视一分钟收费3金币;同时监视两个以上的考场,每监视一分钟收费4金币;当处于两个监考任务之间的空隙之间时,小红会进入待机状态,每分钟消耗1金币。也就是说,直到完成最后一个监考任务之前,小红机器人都会持续消耗金币。
今天小红又来监考,他今天一共要监视n个不同的考场,每个考场的考试开始时间和结束时间都不同,为简化表达,将时间简化为整数代表的时间单位,时间从0开始。
请你计算小红今天的监考任务能够收取多少金币?
第一行一个整数 n 表示小红今天的监考考场数量
接下来 n 行,给出由空格分开的两个整数ai,bi。表示 n 个考场考试的开始时间 ai 与结束时间 bi ,也就是小红开始监考与结束监考的时间(闭区间),保证结束时间大于起始时间
1⩽n⩽10000
0⩽ai,bi⩽106
一个整数,代表小红今天监考所能赚取的金币
输入
3
1 5
4 6
6 6
输出
21