oj.uz

Submission #102829

# Submission time Handle Problem Language Result Execution time Memory
102829 2019-03-27T19:51:46 Z pavel Editor (BOI15_edi) C++14
35 / 100
 3000 ms 359800 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 353400 KB Output is correct
2 Correct 386 ms 353528 KB Output is correct
3 Correct 349 ms 353460 KB Output is correct
4 Correct 342 ms 353272 KB Output is correct
5 Correct 538 ms 353400 KB Output is correct
6 Correct 335 ms 353400 KB Output is correct
7 Correct 397 ms 353616 KB Output is correct
8 Correct 370 ms 353400 KB Output is correct
9 Correct 337 ms 353660 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 359748 KB Output is correct
2 Correct 525 ms 359800 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 357808 KB Output is correct
2 Execution timed out 3071 ms 356200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 353400 KB Output is correct
2 Correct 386 ms 353528 KB Output is correct
3 Correct 349 ms 353460 KB Output is correct
4 Correct 342 ms 353272 KB Output is correct
5 Correct 538 ms 353400 KB Output is correct
6 Correct 335 ms 353400 KB Output is correct
7 Correct 397 ms 353616 KB Output is correct
8 Correct 370 ms 353400 KB Output is correct
9 Correct 337 ms 353660 KB Output is correct
10 Correct 527 ms 359748 KB Output is correct
11 Correct 525 ms 359800 KB Output is correct
12 Correct 501 ms 357808 KB Output is correct
13 Execution timed out 3071 ms 356200 KB Time limit exceeded
14 Halted 0 ms 0 KB -