ds 4.2 食堂打饭

/*************** Problem from : Problem describe : 维护最大值形成的单调递减数组 例如 1-2-3-5-7-2-3-5 那么 在 7还没OUT之前 7前面的1 2 3 5阶段查询结果最大值均为 7 所以在 7 OUT之前 1 2 3 5都是无效的 7 OUT之后 2-3-5同理 2 3 也是无效的 data:2016.12.3 ****************/ #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<stack> #include<queue> #include<ctime> #include<cstring> #include<vector> #include<string> #define ll __int64 #define inf 0x3f3f3f3f3f using namespace std; const int maxn = 100005; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int i, n, ans=0, x; int num[maxn]={0}, Max_v[maxn]={0}, lenNum=0, k=0, lenMax=0, t=0; char op[10]; while(~scanf("%s", op), op[0]!='E') { if(op[0]=='I') { scanf("%d", &x); num[lenNum++] = x; while(lenMax>t && Max_v[lenMax-1] < x) lenMax--; Max_v[lenMax++]=x; } else if(op[0]=='Q') { printf("%d\n", (lenMax==t)?-1:Max_v[t]); } else if(op[0]=='O') { if(k>=lenNum) continue; if(num[k] == Max_v[t]) t++; k++; } } return 0; }