rt,题目如下

题目描述

一条街道上有n个路灯排成一排，编号 1,2,...,n。小 Z 喝醉了，初始在时刻 0 时站 在 1 号路灯旁。 小 Z 从某个时间 t0 ( t0 >= 0 ) 开始游走。在时间 t0 之后，小 Z 每隔一个单位时间就会移 动到相邻的路灯旁。如果小 Z 在时间 t 在 i 号路灯旁，则他在时间 t+1 必然移动到 i-1 号路灯或 i+1 号路灯旁。特殊的，小 Z 不会移动到街道边界之外，即他始终只 停留在路灯 1 和 n 之间（包含边界）。例如，小 Z 在时间 t0+1 必然在 2 号路灯旁。 你得知了一些路人提供的信息，每条信息都可以用整数pi和qi表示，代表在qi时刻某 位路人看到到小 Z 在路灯 pi 旁边。你想找到小 Z 开始到处走动的时间 t0 。在收到信息 的同时，你还想根据当前收到的信息推断 t0 可能的最大值和最小值。 路人提供的信息也有可能不一致。一旦你发现提供的信息有矛盾，只需停止计算并报告 信息不一致。

输入格式

从 drunkard.in 文件读入数据。

第一行包含两个整数 n 和 m，代表路灯的数量和操作次数。

接下来 m 行分别包含一个操作 opi ​ ，格式为以下其一：

clue pi qi ​ ：行人在时间 qi 看到小 Z 在灯柱 pi 旁边。 min：你想根据当前收到的信息推断 t0 的最小可能值。 max：你想根据当前收到的信息推断 t0 的最大可能值。

输出格式

输出到 drunkard.out 文件。

对于每个 min 或 max 操作，输出问题的答案。

对于 max 操作，如果 t0 可以为任意大的数（即不存在一个有限的最大值），那么答案为字符串 inf。

如果当前收到的信息不一致，那么答案为字符串 bad。

样例

输入数据 1

10 7

clue 1 3

min

clue 3 5

max

clue 10 6

max

min

输出数据 1

1

3

bad

bad

样例解释

在第 1 条线索后，小 Z 可能在时间 1 开始向灯柱 2 走动，在时间 2 向灯柱 1 走动，但是不可能是由时间 0 便开始走动的。 在第 2 条线索后，小 Z 必须在时间 3 开始由灯柱 1 (从第 1 条线索得知) 向灯柱 3 走动，才能在时间 5 抵达灯柱 3。 在第 3 条线索后，即使小 Z 在时间 5 开始由灯柱 3 (从第 2 条线索得知) 向灯柱 10 走动，仍然不可能在时间 6 抵达灯柱 10。

数据范围

对于所有数据，

10≤?≤10^9，

1≤?≤2×10^5，

1≤??≤?，

0≤??≤10^9 ，

存在至少一个 min 或 max 操作，

opi为 clue、min 或 max之一。

47分代码如下

#include <bits/stdc++.h>
using namespace std;
set<pair<int, int>>st;
bool bad = false;
int maxx = 2e9, pos = 2e9, last = -1;
/*maxx为目前答案的max  pos是最后一个信息中pi为1的下一条信息(按时间排序后)的qi
last是目前与下一条(按时间排序后)信息的奇偶性不同的最晚的信息 last==-1时目前所有信息奇偶性相同
*/
int main() {
	freopen("drunkard.in", "r", stdin);
	freopen("drunkard.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		string s;
		cin >> s;
		int p, q;
		if (s == "clue") {
			cin >> p >> q;
			if (q - (p - 1) < 0) {
				bad = true;
				continue;
			}
			if (p > 1) {
				pos = min(pos, q);
				maxx = min(maxx, q - (p - 1));
			}
			st.insert({q, p});
			auto now = st.find({q, p});
			if (now != st.begin() && next(now) != st.end() && last == (next(now) -> first))//奇偶性可能有变动 所以重置了重算
				last = -1;
			if (now != st.begin()) { //如果不是时间最早的信息
				auto pre = *prev(now);
				if (((pre.first + pre.second) % 2) != ((p + q) % 2)) //与上一条信息(按时间排序后)的奇偶性不同
					last = max(last, q);
				if (abs(pre.second - p) > abs(pre.first - q))
					bad = true;
			}
			if (next(now) != st.end()) { //如果不是时间最晚的信息
				auto nxt = *next(now);
				if (((nxt.first + nxt.second) % 2) != ((p + q) % 2)) //与下一条信息(按时间排序后)的奇偶性不同
					last = max(last, nxt.first);
				if (abs(nxt.second - p) > abs(nxt.first - q))
					bad = true;
			}
			if (last > pos)
				bad = true;
			/*时间为last的消息与上一条消息(按时间排序后)奇偶性不同 且上一条信息(按时间排序后)对应的路灯编号不为1
			则一定不合法
			*/
		} else if (s == "min") {
			int ans;
			if (bad) {
				cout << "bad\n";
				continue;
			} else if (last != -1) {
				auto ptr = st.lower_bound({last, 0}); //找到last记录的信息
				auto pre = *prev(ptr);
				ans = pre.first + 1;
			} else {
				if (st.size() == 0)
					ans = 0;
				else {
					auto ptr = *st.begin();
					ans = (ptr.first + ptr.second + 1) % 2;
				}
				/*如果时间最早的信息的pi与qi奇偶性不同 那一定在0出发 这样奇数单位时间一定在编号为偶数的路灯
				反之一定在1出发 这样奇数单位时间一定在编号为奇数的路灯
				*/
			}
			printf("%d\n", ans);
		} else {
			if (bad)
				cout << "bad\n";
			else if (maxx == 2e9)
				cout << "inf\n";
			else
				cout << maxx << "\n";
		}
	}
	return 0;
}