Submission #1104311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104311		vjudge1	Wall (IOI14_wall)	C++98	0 / 100	98 ms	16228 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

class SegmentTree{
    private:
    int n;
    vector<int> tree,lazyMax,lazyMin;
    void propagate(int start,int end,int node){
        if(start!=end){
            if(lazyMax[node]!=INT_MIN){
                lazyMax[node*2]=max(lazyMax[node*2],lazyMax[node]);
                lazyMax[node*2+1]=max(lazyMax[node*2+1],lazyMax[node]);
                tree[node]=max(tree[node],lazyMax[node]);
            }
            if(lazyMin[node]!=INT_MAX){
                lazyMin[node*2]=min(lazyMin[node*2],lazyMin[node]);
                lazyMin[node*2+1]=min(lazyMin[node*2+1],lazyMin[node]);
                tree[node]=min(tree[node],lazyMin[node]);
            }
        }
        lazyMax[node]=INT_MIN;
        lazyMin[node]=INT_MAX;
    }
    void updateMax(int start,int end,int l,int r,int val,int node){
        propagate(l,r,node);
        if(r<start||l>end) return;
        if(start<=l&&r<=end){
            tree[node]=max(tree[node],val);
            lazyMax[node]=max(lazyMax[node],val);
            return;
        }
        int mid=(l+r)/2;
        updateMax(start,end,l,mid,val,node*2);
        updateMax(start,end,mid+1,end,val,node*2+1);
        tree[node]=max(tree[node*2],tree[node*2+1]);
    }
    void updateMin(int start,int end,int l,int r,int val,int node){
        propagate(l,r,node);
        if(r<start||l>end) return;
        if(start<=l&&r<=end){
            tree[node]=min(tree[node],val);
            lazyMin[node]=min(lazyMin[node],val);
        } 
        int mid=(l+r)/2;
        updateMin(start,end,l,mid,val,node*2);
        updateMin(start,end,mid+1,end,val,node*2+1);
        tree[node]=min(tree[node*2],tree[node*2+1]);
    }
    int query(int pos,int l,int r,int node){
        propagate(l,r,node);
        if(l==r) return tree[node];
        int mid=(l+r)/2;
        if(pos<=mid) return query(pos,l,mid,node*2);
        else return query(pos,mid+1,r,node*2+1);
    }
    public:
    void init(int s){
        n=s;
        tree.resize(4*n,0);
        lazyMax.resize(4*n,INT_MIN);
        lazyMin.resize(4*n,INT_MAX);
    }
    void updateMax(int l,int r,int val){
        updateMax(l,r,0,n-1,val,1);
    }
    void updateMin(int l,int r,int val){
        updateMin(l,r,0,n-1,val,1);
    }
    int query(int x){
        return query(x,0,n-1,1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    SegmentTree Tree;
    Tree.init(n);
    for(int i=0;i<k;i++){
        if(op[i]==1) Tree.updateMax(left[i],right[i],height[i]);
        else Tree.updateMin(left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++) finalHeight[i]=Tree.query(i);
}

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