hiho1299&hihocoder挑战赛20-t1:打折机票 – 我是思博

代码

话说昨天我在hihocoder找数学期望练习题时,无意中发现了hihocoder有挑战赛!发现的时候,已经开赛了有十多分钟了,我匆忙地参加了比赛。

首先,我打开了第一题:

#1299 : 打折机票

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

因为思念新宿的"小姐姐"们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包。经过了几天的夜战,岛娘终于在体力耗尽之前,用Python抓下了所有6月份,上海至东京的全部共 n 张机票。现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的,最贵的机票。

输入

输入数据的第一行包含两个整数 n, m(1 ≤ n, m ≤ 105),分别表示机票的总数,和询问的总数。接下来的 n 行,每行两个整数 t, v (1 ≤ t, v ≤ 105),表示每张机票出发的时间和价格。 接下来的 m 行,每行两个整数 a, b (1 ≤ a ≤ b ≤ 105),表示每个询问所要求的时间区间。

输出

对于每组询问,输出一行表示最贵的价格。如果没有符合要求的机票,输出一行"None"。

样例输入
7 6
1 1
2 1
4 3
4 4
4 5
6 9
7 9
1 7
1 2
6 7
3 3
4 4
5 5
样例输出
9
1
9
None
5
None

嗯..这是一道很有节操的题目,首先我们拥有可爱的男♂孩子,啊♂,然后呢,还他喵还会写代码,还挺会勤俭持家(选最贵的机票),啊,盆友,票子要伐?

可惜,我实在是对伪娘提不起兴♂趣,嗯,咱们还是好好看题吧。

思路:

我第一个想到的就是线段树啦,于是我打了出来。

但是!令我奇怪的是,这棵线段树,不是RE,就是WA,就是TLE!

(好吧其实都是我的错)

然后,我在这道题,生生卡了俩小时.....

对,你没看错,俩小时,而且我一道都没有AC...

我不服,果断把这锅甩给了亲爱的机房的电脑:

QQ截图20160507212952]

嗯,我觉得这个锅,机房的电脑背定了。没错!都是你的错!

然后,第二天,也就是今天,我,决定向hihocoder群友伸手——求助= =

然后,有几个致命的错误:

  1. 我特么把大数组存为临时变量了;
  2. 我没及时return.

然后这些错误给亲爱的群友11提出来,我修改了后:

QQ截图20160507213234

是的,我顶多改了三句代码

然后

AC

 

 

 

QQ图片20160426181731

来,让我先Orz一下

 

这个故事教训我

我特么就是个

思博

湿笔

 

让我满脑子CNM地,贴上我的AC代码...

 

 

#include
#include
#include
#define MAXN 400100
using namespace std;
int l[MAXN], r[MAXN];
struct Node{
	int l, r, v;
}node[MAXN];

void build(int i, int l, int r){
//	if (l > r) return;
//	cout << i << " " <<  l << " " <<  r << endl;
	node[i].l = l;
	node[i].r = r;
	node[i].v = -1;
	if (l == r) return;
	build(i << 1, l, (l + r) >> 1);
	build((i << 1) + 1,((l + r) >> 1) + 1, r);	
}

int query(int i, int l, int r){
//	cout << i << endl; 
	int s = -1;
	if (node[i].l > r || node[i].r < l) return s;
	if (node[i].l >= l && node[i].r <= r) return node[i].v;
	if (node[i].l == node[i].r) return s;
	int mid = i << 1;
	s = max(s, query(mid, l, r));
	s = max(s, query(mid + 1, l, r));
	return s;
}

void insert(int i, int v, int n){
//	cout << i << " " << node[i].l << " " << node[i].r << endl;
	
	if (node[i].l > n || node[i].r < n) return;
	if (node[i].l <= n && node[i].r >= n) node[i].v = max(node[i].v ,v);
//	cout << i << endl;
	int l = node[i].l, r = node[i].r;
	if (l == r){
		return;
	}
	insert(i << 1, v, n);
	insert((i << 1) + 1, v, n);

}
int main(){
	int n, m;
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);
	scanf("%d%d", &n, &m);

	int bt = -1;
	for (int i = 0; i < n; i++){
		scanf("%d%d", &l[i], &r[i]);
		bt = max(l[i], bt);
	}
//	cout << bt << endl;
	build(1, 1, bt + 1);
	for (int i = 0; i < n; i++){
		insert(1, r[i], l[i]);
	}
//	cout << query(1, 4, 5) << " xxsxsxs" << endl;
	for (int i = 0; i < m; i++){
		scanf("%d%d", &l[i], &r[i]);
//		cout << l[i] << " " << r[i] << endl; 
	}
	for (int i = 0; i < m; i++){
		int a = query(1, l[i], r[i]);
		if (a != -1){
			printf("%dn", a);
		}else{
			printf("Nonen");
		}
	}
	return 0;
}

我还没有学会写个人说明!

发表评论

电子邮件地址不会被公开。 必填项已用*标注