Mayor's posters

Time Limit: 3000ms
Memory Limit: 131072KB

This problem will be judged on UVA. Original ID: 10587
64-bit integer IO format: %lld      Java class name: Main

 
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:

  • Every candidate can place exactly one poster on the wall.
  • All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
  • The wall is divided into segments and the width of each segment is one byte.
  • Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.

Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 ≤ n ≤ 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 ≤ i ≤ n, 1 ≤ li ≤ ri ≤ 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,... , ri.

For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.

Sample input

1

5

1 4

2 6

8 10

3 4

7 10

Output for sample input

4

解题：线段树+离散化。挂了几次，居然还有贴在10-10这样位置的数据，简直太疯狂了。。这能贴么，一个点啊！好吧，改正后，终于Ac 了。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #include <map>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 set<int>st;

 int a[maxn],b[maxn];

 struct node{

     int lt,rt,flag;

 };

 node tree[maxn<<];

 int lisan[maxn<<];

 void build(int lt,int rt,int v){

     tree[v].lt = lt;

     tree[v].rt = rt;

     tree[v].flag = ;

     if(lt +  == rt) return;

     int mid = (lt+rt)>>;

     build(lt,mid,v<<);

     build(mid,rt,v<<|);

 }

 void update(int lt,int rt,int v,int val){

     if(lisan[tree[v].lt] == lt && lisan[tree[v].rt] == rt){

         tree[v].flag = val;

         return;

     }

     if(tree[v].flag){

         tree[v<<].flag = tree[v<<|].flag = tree[v].flag;

         tree[v].flag = ;

     }

     int mid = (tree[v].lt+tree[v].rt)>>;

     if(rt <= lisan[mid]){

         update(lt,rt,v<<,val);

     }else if(lt >= lisan[mid]){

         update(lt,rt,v<<|,val);

     }else{

         update(lt,lisan[mid],v<<,val);

         update(lisan[mid],rt,v<<|,val);

     }

 }

 void query(int v){

     if(tree[v].flag){

         if(!st.count(tree[v].flag)) st.insert(tree[v].flag);

         return;

     }

     if(tree[v].lt+ == tree[v].rt) return;

     query(v<<);

     query(v<<|);

 }

 int main() {

     int t,i,j,n,cnt,tot;

     scanf("%d",&t);

     while(t--){

         tot = ;

         scanf("%d",&n);

         for(i = ; i <= n; i++){

             scanf("%d %d",a+i,b+i);

             if(a[i] > b[i]) swap(a[i],b[i]);

             lisan[tot++] = a[i];

             lisan[tot++] = ++b[i];

         }

         sort(lisan+,lisan+tot);

         cnt = ;

         for(i = ; i < tot; i++){

             if(lisan[i] == lisan[cnt]) continue;

             lisan[++cnt] = lisan[i];

         }

         build(,cnt,);

         for(i = ; i <= n; i++) update(a[i],b[i],,i);

         st.clear();

         query();

         printf("%d\n",st.size());

     }

     return ;

 }

最新文章

  1. Ajax_02之XHR发起异步请求
  2. 移动端图片滚动加载-lazyload实现的要点总结
  3. python 测试驱动开发的简单例子
  4. 深入浅出ECharts系列（一）地图+散点图
  5. OD: Windows Driver Fuzz
  6. SQL Server自定义函数( 转载于51CTO )
  7. python自学笔记（四）python基本数据类型之元组、集合、字典
  8. 要引入java吸管工具
  9. /MD、/MT、/LD（ 使用 多线程版本 运行时库的C runtime library)
  10. springboot--mybatis--pagehelper分页整合不起作用
  11. 译文 - Recommender Systems: Issues, Challenges, and Research Opportunities
  12. Codeforces round FF
  13. 在 浏览器中调用外接设备— —手写板 【win10 x64 手动注册ocx控件的方法】
  14. docker_File 执行报错总结
  15. 校验总结:校验是否是中英文等等(1.正则校验 2.hibernate volidator)
  16. elasticsearch安装servicewrapper插件
  17. 如何将Mac系统OS X Yosemite装到外部磁盘？（转）
  18. Python入门之Python Colorama模块
  19. BZOJ 3524 Couriers | 主席树
  20. errorlevel 续2

热门文章

  1. Objective-C 声明属性
  2. bzoj 1599: [Usaco2008 Oct]笨重的石子【枚举】
  3. 基于.Net Core的API框架的搭建（3）
  4. Invalid default value for &#39;create_date&#39; timestamp field
  5. Poj 3694 Network (连通图缩点+LCA+并查集)
  6. Joseph UVA 1452 Jump
  7. ACM_抢糖果
  8. 块级标签与预格式化文本标签----------大多数XHTML可以表示为两种类型的标签：块标签（block tag）和内联标签（inline tag）
  9. 转 MySQL数据库基础
  10. es6 export-from用法