问题 27137 --TCP网络协议

27137: TCP网络协议

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

在如今的网络中,TCP是一种被广泛使用的网络协议,它在传输层提供了可靠的通信服务。众所周知,网络是存在时延的,例如用户先后向服务器发送了两个指令op1op2,并且希望服务器先处理指令op1,再处理指令op2;但由于网络时延,这两个指令可能会失序到达,而导致服务器先执行了指令op2,这是我们不希望看到的。TCP协议拥有将失序到达的报文按顺序重组的功能,一种方法是给每一个报文打上一个时间戳。而你今天要实现的功能比这个要简单很多。我们需要你维护一个服务器,这个服务器的功能是一个简单的栈,你会接收三种用户的指令:

push x t --- 表示将x元素入栈,这条指令的时间戳为t

pop t --- 表示将栈顶元素弹出,这条指令的时间戳为t

peak t --- 用户询问现在栈顶元素的值,这条指令的时间戳为t

 

当一条时间戳为t的指令到达时,你需要进行如下处理:

1.将所有之前执行的时间戳大于tpushpop指令全部撤销

2.执行当前这条指令

3.按时间戳顺序重新执行在第1步被撤销的指令

 

注意你不需要撤销以及重新执行之前已经执行过的peak指令,也就是说每一条peak指令只有在它到达的时候会被执行一次。

 

我们保证每一条指令的时间戳都是唯一的;若你在需要执行一条pop指令时发现当前栈为空,则当前你可以忽略这条指令。

输入

第一行包含一个整数n,表示指令总数。

接下来n行按指令到达服务器的顺序给出每一条指令,有三种类型

push x t

pop t

peak t

输出

对于每一条peak指令,输出对应的答案占一行;若栈为空,输出-1

样例输入

7
push 100 3
push 200 7
peak 4
push 50 2
pop 5
peak 6
peak 8

样例输出

100
50
200

提示


数据范围:



对于10%的数据,1 <= n <= 1000



对于40%的数据,1 <= n <= 80000



对于100%的数据,1 <= n <= 3000000 <= xt <= 1000000000

来源

 

[提交][状态]