【线段树】BAPC2014 E Excellent Engineers (Codeforces GYM 100526)
2024-08-29 12:35:24
题目链接:
http://codeforces.com/gym/100526
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11668&courseid=0
题目大意:
N个人,每个人有三个能力排名X Y Z,每种能力没有同名次,如果当前的人比在清单上的人中至少有一项能力都要优,则这个人也会被加到清单上。
求最终清单上有几个人。(N<=100000)
题目思路:
【线段树】
首先按第三关键字排序,确定一维的大小关系,接下来如果(X,Y)中的其中一个比之前的人都要优,则这个人就会被添加。
考虑用a[X]表示1到X中最小的Y值,则只需要比较Y和a[X]的大小就能确定出是否需要添加这个人。
用线段树记录区间最小Y值,并且实时更新。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 100004
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
struct xxx
{
int x,y,z;
}a[N];
int t[N<<];
bool cmp(xxx aa,xxx bb)
{
return aa.x<bb.x;
}
void change(int l,int r,int x,int c,int k)
{
if(l>r || x<l || x>r)return;
if(l==r){t[k]=c;return;}
change(l,(l+r)>>,x,c,k+k);
change((l+r)/+,r,x,c,k+k+);
t[k]=min(t[k+k],t[k+k+]);
}
int query(int l,int r,int a,int b,int k)
{
if(l>r || l>b || r<a)return MAX;
if(a<=l && r<=b)return t[k];
int x1=query(l,(l+r)>>,a,b,k+k),x2=query((l+r)/+,r,a,b,k+k+);
return t[k]=min(x1,x2);
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
for(scanf("%d",&cas);cas;cas--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s+1))
// while(~scanf("%d",&n))
{
ans=;mem(t,0x7f);
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d%d%d",&a[i].y,&a[i].z,&a[i].x);
sort(a+,a++n,cmp);
change(,n,a[].y,a[].z,);
for(i=;i<=n;i++)
{
j=query(,n,,a[i].y,);
if(j>a[i].z)ans++;
change(,n,a[i].y,a[i].z,);
}
printf("%d\n",ans);
}
return ;
}
/*
// //
*/
最新文章
- 模拟赛1103d1
- Advacned Puppet: Puppet Master性能调优
- vs2015启动iis express失败
- CQOI2009中位数图
- URAL 1019 - Line Painting
- .Net下的进程间的通讯 -- Windows消息队列
- [CF161D]Distance in Tree-树状dp
- 如何开发自己的搜索帝国之安装ik分词器
- 关于java中的伪共享的认识和解决
- linux的文件打包与压缩
- Android Studio2.0 教程从入门到精通Windows版 - 提高篇
- mysql表分区案例
- sklearn 的train_test_split
- 创建sequence和触发器出现权限不足
- node.js连接MongoDB数据库,db.collection is not a function完美解决
- 【Robot Framework 项目实战 01】使用 RequestsLibrary 进行接口测试
- android app 的插件化、组件化、模块化开发
- Ubuntu 12.04解决重启后resolv.conf清空的问题
- RIDE指定log和report的输出目录
- Xcode 5.1安装插件:规范凝视生成器VVDocumenter