Time Limit: 2 second(s) | Memory Limit: 64 MB |
Given n segments (1 dimensional) and q points, for each point you have to find the number of segments which contain that point. A point pi will lie in a segment A B if A ≤ pi ≤ B.
For example, if the segments are (6 12), (8 8), (10 12), (8 11), (0 12) and the point is 11, then it is contained by 4 segments.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 50000) and q (1 ≤ q ≤ 50000).
Each of the next n lines contains two integers Ak Bk (0 ≤ Ak ≤ Bk ≤ 108) denoting a segment.
Each of the next q lines contains an integer denoting a point. Each of them range in [0, 108].
Output
For each case, print the case number in a single line. Then for each point, print the number of segments that contain that point.
Sample Input |
Output for Sample Input |
1 5 4 6 12 8 8 10 12 8 11 0 12 11 12 2 20 |
Case 1: 4 3 1 0 |
Notes
Dataset is huge, use faster I/O methods.
题意:
给出 T (<= 5)组数据,后给出 N(1 ~ 50000) 和 Q(1 ~ 50000),代表有 N 个区间和 Q 个数,后给出 N 个区间和 Q 个数的询问,问 Q 这个数被覆盖了多少次,数的范围是 0 ~ 10 ^ 8。
思路:
区间统计 + 离散化。给出 50000 个数,极限情况也就有 3 X 50000 个不同的数,故数组不需要开到 10 ^ 8,只需要开到离散后的极限值就好。区间统计方法是 起点++,(终点 + 1)--,最后统计后一项等于该项 + 前一项的值。最后输出结果即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int MAX = 50005 * 3; int l[MAX], r[MAX], ask[MAX]; int num[MAX], res[MAX]; int main() { int t; scanf("%d", &t); for (int tt = 1; tt <= t; ++tt) { int n, m, ans = 0; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d%d", &l[i], &r[i]); num[ ans++ ] = l[i]; num[ ans++ ] = r[i]; } for (int i = 0; i < m; ++i) { scanf("%d", &ask[i]); num[ ans++ ] = ask[i]; } sort(num, num + ans); ans = unique(num, num + ans) - num; memset(res, 0, sizeof(res)); for (int i = 0; i < n; ++i) { int f = lower_bound(num, num + ans, l[i]) - num; int t = lower_bound(num, num + ans, r[i]) - num; ++res[f]; --res[t + 1]; } for (int i = 0; i < ans; ++i) res[i] += res[i - 1]; printf("Case %d:\n", tt); for (int i = 0; i < m; ++i) { int a = lower_bound(num, num + ans, ask[i]) - num; printf("%d\n", res[a]); } } return 0; }
相关推荐
vox-5segments.pth.tar
Circle Segments 可视化技术应用研究,程一博,胡俊,本文主要对Circle Segments可视化技术的应用做了研究。通过对比该技术在不同UCI数据集上的可视化结果,展示了其强大的可视化能力。通过
ThisbookteachesC++... The code segments and their detailed explanations show how easy it is to implement advanced algorithms such as finite elements and multigrid.
% segments in the result with largest area, and in case less than seven % segments were found, it attempts to recall the function, making the % separation between the already found segments clearer...
无限维Teichmuller空间中测地线的一点注记,胡韻,沈玉良,本文证明了在任意无限维Teichm
segments.gen
资源来自pypi官网。 资源全名:ligo_segments-1.0.1-cp35-cp35m-manylinux1_x86_64.whl
主要包含kAS的文档和PPT,以及相关的文献。之前导师让做kAS报告时收集的资料,请需要的下载。
router-segments使用来匹配路由路径, , 和许多其他路由器也使用该路径。 import { createRouterBuilder } from 'router-segments' ; const builder = createRouterBuilder ( ) ; builder . add ( '/' , ref ) ; ...
Visifire让你利用ASP、A line chart or line graph is a type of chart which displays information as a series of data points called 'markers' connected by straight line segments.[1] It is a basic type of ...
IMPROVED SPEAKER SEGMENTATION AND SEGMENTS CLUSTERING USING THE BAYESIAN INFORMATION CRITERION(Alain Tritschler and Ramesh Gopinath)
- ADD: In TFlexPanel.DefaultLinkPoint property added Size field that lets define visual size of the connection points of the flex-connectors. Initialized with DefaultLinkPointSize constant in the ...
Recent developments in laser scanning technologies have provided innovative solutions for acquiring three-dimensional (3D) point clouds about road corridors and its environments. Unlike traditional ...
We also allow the user to specify the deformations usingeither sets of points or line segments, the later useful for control-ling curves and profiles present in the image. For each of thesetechniques...
Discovering and segmenting objects in videos is a challenging task due to large variations of objects in appearances, deformed shapes and cluttered backgrounds. In this paper, we propose to segment ...
resizing TCP’s segments in order to avoid incurring timeout penalty. We evaluate the merits of the aforementioned solutions using ns-2 simulations. Results show that each of our suggested techniques ...
SegLink on github-Detecting Oriented Text in Natural Images by Linking Segments-附件资源
一般我们可以这样写: 代码如下: string url = Request.Url.ToString(); string r = url.Substring(url.LastIndexOf(‘/’) + 1); Response.Write(r);... 实际上,.Uri类提供了一个Segments属性,其实
富士通单片机MB902420系列The internal LCD-cotroller will be initialised (1/2 bias, 1/2 duty). The internal Resistor devider is used...Some different methods are shown, how segments can be swicthed on/off.