Stars
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 30828 | Accepted: 13471 |
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5 1 1 5 1 7 1 3 3 5 5
Sample Output
1 2 1 1 0
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
题意:
给出 N(1 ~ 15000) ,后给出 N 个 x 和 y 的坐标 [ 0 ~ 32000 ],输入的顺序是以 y 递增的顺序输入的,如果 y 相等,则按 x 递增的顺序输入。每个星星都有一个等级,这个等级等于左下所有星星的数量。输出 0 ~ N - 1 每个等级各含多少颗星星。
思路:
树状数组。
每个星星一给出就可以确定定出等级,因为根据输入的顺序可以得出后面给出的星星是不会影响这颗星星的等级的,所以边输入就可以边统计。等级就是 0 ~ xi 总共含有的星星数量。用树状数组统计算出登记后,再将 xi 添加到数组中即可。有一个注意的地方就是,如果 x == 0 的时候会出现死循环而 TLE ,是因为 add 操作,所以应该要对 x 坐标 + 1 处理。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int bit[32005], ran[15005]; void add(int i, int x) { while (i <= 32005) { bit[i] += x; i += i & -i; } } int sum(int i) { int s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } int main () { int n; scanf("%d", &n); memset(bit, 0, sizeof(bit)); memset(ran, 0, sizeof(ran)); for (int i = 0; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); ++x; ++ran[ sum(x) ]; add(x, 1); } for (int i = 0; i < n; ++i) printf("%d\n", ran[i]); return 0; }
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
绘制太阳系行星轨道2D平面图,数据库中包含了行星数据,但是数据来源于百度搜集,不够精确
DAG上的记忆化树形DP,博弈 有限状态自动机+树形DP 状态压缩DP 炮兵阵地 Help Bob,买匹萨 匹配数量 堆筛子 全排列式状态DP 计算几何 多边形地图染色 数据结构 Hash 枚举+hash,方程解数 点集对称中心 字符...
star manual is a manual for cmg software
Stars1
视觉测量(V-STARS摄影测量系统) 立体视觉是由多幅图像(一般2幅)获取物体三维几何信息的方法
Stars2
stars
按stars排序的论文-代码实现列表,每周更新
m3u8合并器 by stars-one.zip
StarCabinet, 开源的跨平台Github Stars管理分析工具
Baseball Stars 2 (USA) wiiware wad 格式wii 专用,可以放到SD卡内进行安装
Atom-atom-package-diff.zip,安装的Atom软件包与APM Stars之间的差异原子包差异,atom是一个用web技术构建的开源文本编辑器。
Android Five Stars Library Android Five Stars Library is a small library that helps developers add a "Rate My App" dialog to their applications. It's called "Five Stars" because the dialog has a ...
当前版本的STARS是基于从数字到Numpy的重构。 此版本应可在以下平台上使用 Linux 视窗 苹果电脑 安装 使用Conda(所有平台) git clone https://github.com/sjsrey/stars.git 安装 conda create -n stars python...
在Github中stars数最多的Go Web框架集合
上传一个用vc制作的闪闪的红星,能够自定义背景和闪烁速度。你们可以
scor-stars 基于vue的评分星星组件,例如5:glowing_star: 安装 方法一: npm install scor-stars --save import stars from 'scor-stars' 方法二: [removed] 使用 不管您是在.vue文件中使用或者是在原生的html中...
CMG-STARS使用指南适用于初学者,是PDF文件,英语也比较容易看懂。
city of stars.docx