题目名称 2897. 天天爱射击
输入输出 shooting.in/out
难度等级 ★★★☆
时间限制 3000 ms (3 s)
内存限制 512 MB
测试数据 20 简单对比
题目来源 娄晨耀 2018-02-08
开放分组 全部用户
提交状态
分类标签
通过:8, 提交:38, 通过率:21.05%
Gravatarcshwang 100 3.576 s C++
Gravatarcshwang 100 4.809 s C++
Gravatarzjh 100 5.251 s C++
GravatarGKxx 100 5.828 s C++
GravatarGGN_2015 100 6.281 s C++
GravatarGGN_2015 100 6.433 s C++
GravatarHJQwQ 100 7.271 s C++
GravatarHyoi_Turkey 100 7.893 s C++
Gravatarzxf 100 11.428 s C++
Gravatar梦那边的美好ETMN 100 15.524 s C++
关于 天天爱射击 的讨论

2897. 天天爱射击

★★★☆   输入文件:shooting.in   输出文件:shooting.out   简单对比
时间限制:3 s   内存限制:512 MB

题目描述

小C爱上了一款名字叫做《天天爱射击》的游戏,在这款游戏中可以用子弹将木板打碎。如图所示,这个游戏有一些平行于x轴的木板。现在有一些子弹,**按顺序**沿着y轴方向向这些木板射去。第i块木板被S_i个子弹击穿以后,就会碎掉消失。一个子弹可以贯穿其轨迹上的全部木板,特别的,如果一个子弹触碰到木板的边缘,也视为贯穿木板。

小C现在知道了游戏中n块木板位置,以及知道了m个子弹起始位置。现在问你每个子弹射出去以后,有多少木板会被击穿?

输入格式

第一行两个整数n和m,表示木板数量和子弹数量。其中1 <= n,m <= 200,000。

接下来n行,每行3个整数x_1,x_2,S,表示每块木板的左端点x坐标、右端点x坐标,以及贯穿多少次会碎掉。其中保证1 <= x_1 <= x_2 <=200,000 且1 <= S <=200,000。

接下来m行,每行一个整数x,表示每个子弹的x坐标。子弹按照发射顺序给出。其中保证1 <= x <= 200,000。

输出格式


m 行,每行一个整数。表示每颗子弹射出去后,有多少木板碎掉。

样例输入


3 2

1 3 1

2 4 2

3 4 1

2

3

样例输出



1

2

数据范围及提示

对于30%的数据,n,m <= 1000,其余按题目描述所示

对于100%的数据,n,m <= 200,000,其余按题目描述所示