Submission #102829

#	Time	Username	Problem	Language	Result	Execution time	Memory
102829		pavel	Editor (BOI15_edi)	C++14	35 / 100	3071 ms	359800 KiB

edi

#include <cstdio>
#include <stack>
#include <set>

using namespace std;
typedef pair<int,int> ii;

const int MAXN = 1<<19;

int n;
stack<int> a[MAXN];
int b[MAXN], p[MAXN];
int seg[2*MAXN];

void add(int x, int idx){
    a[x].push(idx);
    seg[MAXN+x]=a[x].top();
    for(int i=(MAXN+x)/2;i>0;i/=2){
        seg[i]=max(seg[i*2], seg[i*2+1]);
    }
}

void rem(int x){
    a[x].pop();
    if(a[x].empty()) seg[MAXN+x]=-1;
    else seg[MAXN+x]=a[x].top();
    for(int i=(MAXN+x)/2;i>0;i/=2){
        seg[i]=max(seg[i*2], seg[i*2+1]);
    }
}

int query(int node, int nl, int nr, int l, int r){
    if(nl>r || nr<l) return -1;
    if(l<=nl && nr<=r) return seg[node];
    return max(query(node*2, nl, nl+(nr-nl)/2, l, r),
               query(node*2+1, nl+(nr-nl)/2+1, nr, l, r));
}

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;++i){
        scanf("%d", &b[i]);
        if(b[i]>0){
            p[i]=i;
            add(0, i);
        }else{
            p[i]=query(1, 0, MAXN-1, 0, -b[i]-1);
            add(-b[i], i);
            bool d=true;
            for(int j=p[i];;j=p[j]){
                if(d){
                    if(b[j]>0) {rem(0);break;}
                    else rem(-b[j]);
                }else{
                    if(b[j]>0) {add(0, j);break;}
                    else add(-b[j], j);
                }
                d=!d;
            }
        }
        int k = query(1, 0, MAXN-1, 0, 0);
        if(k==-1) puts("0");
        else printf("%d\n", b[k]);
    }
}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
edi.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37