Submission #7546

# Submission time Handle Problem Language Result Execution time Memory
7546 2014-08-11T03:00:17 Z Namnamseo Wall (IOI14_wall) C++
0 / 100
196 ms 197756 KB
#include "wall.h"

const int inf = 2147480000;

struct Node {
    int rangel,ranger;
    Node *lc, *rc;
    int minval,maxval;
    Node(int left,int right) {
        minval=0; maxval=inf;
        rangel = left; ranger = right;
        if(left==right) return;
        int mid = (left+right)>>1;
        lc = new Node(left,mid);
        rc = new Node(mid+1,right);
    }
    void applyRange(int nmin,int nmax){
        if(minval<nmin){
            minval = nmin;
            if(maxval<nmin) maxval=nmin;
        }
        if(nmax<maxval){
            nmax=maxval;
            if(nmax<minval) minval=nmax;
        }
    }
    void updateRange(int l,int r,int newmin,int newmax){
        if(l<=rangel && ranger <= r){
            applyRange(newmin,newmax);
        } else {
            if(r<rangel || ranger < l) return;
            lc->applyRange(minval,maxval);
            rc->applyRange(minval,maxval);
            minval=0; maxval=inf;
            lc->updateRange(l,r,newmin,newmax);
            rc->updateRange(l,r,newmin,newmax);
        }
    }
    int answer(int pos){
        if(pos=rangel && pos==ranger) return minval;
        int ret = ((pos<=((rangel+ranger)/2))?lc:rc)->answer(pos);
        if(ret<minval) return minval;
        if(maxval<ret) return maxval;
        return ret;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Node* root = new Node(0,2097151);
    int i;
    for(i=0;i<k;i++) {
        if(op[i]) root->updateRange(left[i],right[i],height[i],inf);
        else root->updateRange(left[i],right[i],0,height[i]);
    }
    for(i=0;i<n;i++){
        finalHeight[i]=root->answer(i);
    }
    return;
}
# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 197756 KB Program hung waiting for input
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 197756 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 197756 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 197756 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -