10.0 s

256 MB

standard input

standard output

As an ACM-ICPC newbie, Aishah is learning data structures in computer science. She has already known that a stack, as a data structure, can serve as a collection of elements with two operations:

• push, which inserts an element to the collection, and
• pop, which deletes the most recently inserted element that has not yet deleted.

Now, Aishah hopes a more intelligent stack which can display the maximum element in the stack dynamically. Please write a program to help her accomplish this goal and go through a test with several operations.

Aishah assumes that the stack is empty at first. Your program will output the maximum element in the stack after each operation. If at some point the stack is empty, the output should be zero.

The input contains several test cases, and the first line is a positive integer T

into the stack and the procedure POP() pops the topmost element in the stack or does nothing if the stack is empty.

For each test case, output a line containing Case #x: y, where x is the test case number starting from 1

means bitwise xor.

The first test case in the sample input has 4

 #include<bits/stdc++.h>

 typedef long long ll;

 using namespace std;

 int n,p,q,m;bool adf;

 long long ans;

 unsigned int SA,SB,SC;

 long long last,sttp,dsttp;

 stack<long long> st,dst;

 unsigned int rng61(){

     SA^=SA<<;

     SA^=SA>>;

     SA^=SA<<;

     unsigned int t=SA;SA=SB;

     SB=SC;

     SC^=t^SA;

     return SC;

 }

 void gen(){

     scanf("%d%d%d%d%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC);

     while(st.size())st.pop();while(dst.size())dst.pop();

     ans=;

     for(unsigned int i=;i<=n;i++){

         adf=;

         if(dst.empty())dst.push();

         if(rng61()%(p+q)<p)st.push(rng61()%m+);

         else if(st.size()) last=st.top(),st.pop(),adf=;

         if(st.empty()){

             ans^=i*;

             while(dst.size())dst.pop();

             dst.push();

         }

         else {

             sttp=st.top(),dsttp=dst.top();

             if(adf){

                 if(sttp>=dsttp)dst.push(sttp);

             }

             else {

                 if(last>=dsttp&&dst.size())dst.pop();

             }

             if(dst.empty())dst.push();

             ans^=i*dst.top();

         }

     }

 }

 int main(){

     int T,cas=;

     scanf("%d",&T);

     while(T--){

         gen();

         printf("Case #%d: %lld\n",cas++,ans);

     }

 }

 /**

 给你一个栈和一个叫rng61的算法,当符合条件就加入一些内容到栈中,并在每次操作后记录当前栈中最大值ai,最后输出答案1到n的异或和i*ai

 rng61是优化不了了,但我们可以在找栈中最大值时优化,如果是要询问栈中最大值,那么如果当前加入的元素小于以前记录的最大值,那么这个信息是没有记录的必要的,

 所以可以用一个单调不减的单调栈存每个状态的最大值,另一个普通栈存操作的原始序列,如果要往普通栈中推入元素,则如果这个元素大于等于单调栈的栈顶则加入单调栈,

 如果在普通栈进行pop操作,则看当前pop的元素是否>=单调栈的栈顶,如果是就把单调栈的栈顶pop(因为我们在单调栈中存的是单调不减的元素,所以如果碰到普通栈pop的元素大于等于单调栈栈顶元素,则这个元素必定是加入过单调栈的),

 如果普通栈为空或单调栈为空,则清空单调栈并向单调栈中推入一个0元素

 然后每次操作的普通栈中的最大值就是单调栈的栈顶

 注意栈不为空时才能进行pop操作(如果是数组模拟则tp--后如果tp<0则需要让tp=0),ans要用long long存,这次比赛是算法是写正确了,但实现时用了unsigned int,一直卡在最后的数据,以后像ans,求和,求积之类的果断用long long来存

 **/