xtu数据结构 G. Count the Colors
G. Count the Colors
64-bit integer IO format: %lld Java class name: Main
Your task is counting the segments of different colors you can see at last.
Input
The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
x1 x2 c
x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.
All the numbers are in the range [0, 8000], and they are all integers.
Input may contain several data set, process to the end of file.
Output
Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.
If some color can't be seen, you shouldn't print it.
Print a blank line after every dataset.
Sample Input
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1
Sample Output
1 1
2 1
3 1
1 1
0 2
1 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#define LL long long
#define INF 0x3f3f3f
using namespace std;
const int maxn = ;
struct node {
int lt,rt,color;
} tree[maxn<<];
int col[maxn],temp;
void build(int lt,int rt,int v) {
int mid = (lt+rt)>>;
tree[v].lt = lt;
tree[v].rt = rt;
tree[v].color = -;
if(lt+ == rt) return;
build(lt,mid,v<<);
build(mid,rt,v<<|);
}
void update(int lt,int rt,int c,int v) {
if(lt == rt || tree[v].color == c) return;
if(tree[v].lt >= lt && tree[v].rt <= rt) {
tree[v].color = c;
return;
}
if(tree[v].color >= ) {
tree[v<<].color = tree[v<<|].color = tree[v].color;
tree[v].color = -;
}
int mid = (tree[v].lt+tree[v].rt)>>;
if(rt <= mid) {
update(lt,rt,c,v<<);
} else if(lt >= mid) {
update(lt,rt,c,v<<|);
} else {
update(lt,mid,c,v<<);
update(mid,rt,c,v<<|);
}
tree[v].color = -;
}
void query(int v) {
if(tree[v].color == -) {
temp = -;
return;
}
if(tree[v].color != -) {
if(tree[v].color != temp) {
temp = tree[v].color;
col[temp]++;
}
return;
}
if(tree[v].lt+ != tree[v].rt) {
query(v<<);
query(v<<|);
}
}
int main() {
int n,i,j,x,y,c,mx;
while(~scanf("%d",&n)) {
build(,,);
memset(col,,sizeof(col));
mx = ;
for(i = ; i < n; i++) {
scanf("%d%d%d",&x,&y,&c);
update(x,y,c,);
if(c > mx) mx = c;
}
temp = -;
query();
for(i = ; i <= mx; i++)
if(col[i]) printf("%d %d\n",i,col[i]);
printf("\n");
}
return ;
}
最新文章
- java程序设计之完数
- 通过Maven将Web程序部署到远程Tomcat8服务器的一些注意事项
- 项目搭建系列之一:使用Maven搭建SpringMVC项目
- 《深入浅出WPF》笔记三
- prior knowledge
- echarts -01 入门
- Codeigniter 利用加密Key(密钥)的对象注入漏洞
- 关于SQL IO的一些资料
- I have a dream
- linux nVidia driver 304 319 . installation by hand
- 百度地图API的学习
- label与input之间的对应
- jQuery-easyui和validate表单验证实例
- (常用)subprocess模块 详情官方
- CSS:Float
- 使用ionic开发时用遇到监听手机返回按钮的问题~
- adb push和adb install区别
- MySQL数据库常用操作和技巧
- mysql数据库怎么存入emoji表情,更改utf8mb4后为什么出现全是问号
- Universal-Image-Loader解析(二)——DisplayImageOptions的详细配置与简单的图片加载
热门文章
- android开发学习 ------- 自定义View 圆 ,其点击事件 及 确定当前view的层级关系
- python-mysql软件下载地址
- Selenium私房菜系列5 -- 第一个Selenium RC测试案例
- 【iOS】UITableview cell 顶部空白的n种设置方法
- (十)mybatis之配置(mybatis-config.xml)
- java里面byte数组和String字符串怎么转换
- struts2的动态方法配置
- shell脚本,创建50个文件,删除50个文件。
- base64类
- java在线聊天项目0.7版 连接多个客户端问题,开启多个客户端后服务器端只接收到一个 对各种异常的补充处理