文档章节

hihocoder 1299 打折机票 线段树

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:34
字数 232
阅读 4
收藏 0

题目链接:http://hihocoder.com/problemset/problem/1299

code:

//线段树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100005
using namespace std;
int price[maxn];
int Max[maxn];
int segTree[4*maxn];
int maxtime;
void built(int node,int begin,int end)
{
    if(begin == end){
        segTree[node] = price[begin];
    }
    else{
        built(node*2,begin,(begin+end)/2);
        built(node*2+1,(begin+end)/2+1,end);
        segTree[node] = max(segTree[node*2],segTree[node*2 + 1]);
    }
}
int query(int node,int begin,int end,int left,int right)
{
    int p1, p2;
    if (left > end || right < begin)
        return -1;
    if (begin >= left && end <= right)
        return segTree[node];
    p1 = query(2 * node, begin, (begin + end) / 2, left, right);
    p2 = query(2 * node + 1, (begin + end) / 2 + 1, end, left, right);
    if (p1 == -1)
        return p2;
    if (p2 == -1)
        return p1;
    if (p1 >= p2)
        return  p1;
    return  p2;
}
int main()
{
    int n,m;
    memset(price,0,sizeof(price));
    memset(Max,0,sizeof(Max));
    maxtime = 0;
    cin >> n >> m;
    for(int i = 0;i < n;i ++)
    {
        int t,p;
        cin >> t >> p;
        price[t] = max(price[t],p);
        maxtime = max(maxtime,t);
    }
    built(1,1,maxtime);
    while(m --)
    {
        int a,b;
        cin >> a >> b;
        int ans =  query(1,1,maxtime,a,b);
        if(ans == 0)
            cout << "None" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5499345.html

上一篇: hdu1418 欧拉公式
下一篇: 面向抽象编程
YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
HihoCoder - 1040 矩形判断

矩形判断   给出平面上4条线段,判断这4条线段是否恰好围成一个面积大于0的矩形。 Input   输入第一行是一个整数T(1<=T<=100),代表测试数据的数量。   每组数据包含4行,每行包含4个整...

suvvm
01/28
0
0
2016 ACM/ICPC Asia Regional Beijing Online

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82710099 2016 ACM/ICPC Asia Regional Beijing On...

bryce1010
2018/09/14
0
0
双十二来了,我爬取了淘宝上所有的羽绒服|想找到最大折扣

阅读本文大概需要3分钟 天气越来越冷,北方已经开始下雪了,而在南方的我此刻也冻着瑟瑟发抖,棉衣棉裤早就穿上了,还是取暖基本靠抖!明天就是双十二了,我想买件羽绒服,于是我爬取了淘宝上...

菜鸟学python
2017/12/12
0
0
解决区间第K大的问题的各种方法

例题:http://poj.org/problem?id=2104 最近可能是念念不忘,必有回响吧,总是看到区间第k大的问题,第一次看到是在知乎上有人面试被弄懵了后来又多次在比赛中看到。以前大概是知道怎么解决但...

GoldenFingers
2018/08/17
0
0
2016 ACM/ICPC Asia Regional Beijing Online A.The Book List

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/82700193 2016 ACM/ICPC Asia Regional Beijing On...

bryce1010
2018/09/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS 7 查找软件安装位置的方法

1、通过文件搜索查找 root@jun-virtual-machine:# find / -name "*squid*"/var/log/squid/var/spool/squid/var/lib/yum/yumdb/s/48a7dbee62d6d5962ed739a8e4fc117cf7378bfd-squid-3.5......

webcreazy
11分钟前
5
0
eureka 加入密码认证 springboot-admin 加入密码认证

1. pom.xml 加入依赖 <!-- 加入密码认证 --><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-security</ar......

java框架开发者
15分钟前
4
0
数字在排序数组中出现的次数

Input:nums = 1, 2, 3, 3, 3, 3, 4, 6K = 3Output:4 二分查找的练习 public int GetNumberOfK(int[] nums, int K) { int first = binarySearch(nums, K); int last = b......

Garphy
27分钟前
5
0
大厂面试经:高频率JVM面试问题整理!

JVM(Java虚拟机)简单来说就是运行Java代码的解释器,作为螺丝钉程序员JVM其实了解下就差不多啦,不懂JVM内部细节照样能写出优质的代码!但是一到造火箭、飞机的场景(面试)不懂JVM的你,会...

架构文摘
42分钟前
9
0
thinkphp5.1学习过程五——request

<?phpnamespace app\index\controller;//use \think\facade\Request;use \think\Request;/** * Class Demo3 * @package app\index\controller * 正常情况下,控制器不依赖......

大海yht
52分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部