Submission #7549

#	Time	Username	Problem	Language	Result	Execution time	Memory
7549		Namnamseo	Wall (IOI14_wall)	C++98	100 / 100	1440 ms	213400 KiB

wall

#include "wall.h"
#include <cstdio>

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) {
            maxval=0;
            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){
            maxval=nmax;
            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]==1) 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;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39