Submission #492683

#	Time	Username	Problem	Language	Result	Execution time	Memory
492683		Carmel_Ab1	Wall (IOI14_wall)	C++17	61 / 100	947 ms	262148 KiB

wall

#include<bits/stdc++.h>
using namespace std;


#include "wall.h"

struct seg{
    int l,r,m;
    seg* lp=0,*rp=0;
    int val=-1,propmn=1e9,propmx=-1e9;

    seg (int l,int r):l(l),r(r),m((l+r)/2){
        if(l+1<r){
            lp=new seg(l,m);
            rp=new seg(m,r);
        }
    }

    void applymn(int x){
        propmx=min(propmx,x);
        propmn=min(propmn,x);
        val=min(val,x);
    }
    void applymx(int x){
        propmx=max(propmx,x);
        propmn=max(propmn,x);
        val=max(val,x);
    }
    void pull(){
        if(lp->val==rp->val)
            val=lp->val;
        else
            val=-1;
    }
    void push(){
        lp->applymn(propmn);
        rp->applymn(propmn);
        propmn=1e9;

        lp->applymx(propmx);
        rp->applymx(propmx);
        propmx=-1e9;
    }
    void updmn(int a,int b,int v){
        if(r<=a || b<=l)
            return;
        else if(a<=l && r<=b){
            applymn(v);
            return;
        }
        push();
        lp->updmn(a,b,v);
        rp->updmn(a,b,v);
        pull();
    }
    void updmx(int a,int b,int v){
        if(r<=a || b<=l)
            return;
        else if(a<=l && r<=b){
            applymx(v);
            return;
        }
        push();
        lp->updmx(a,b,v);
        rp->updmx(a,b,v);
        pull();
    }

    int qur(int i){
        if(l+1==r)
            return val;
        push();
        if(i<m)
            return lp->qur(i);
        else
            return rp->qur(i);
    }
};

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
    seg s(0,n+1);
    s.updmx(0,n,0);

    for(int i=0; i<k; i++){
        if(op[i]==1)
            s.updmx(L[i],R[i]+1,H[i]);
        else
            s.updmn(L[i],R[i]+1,H[i]);
    }
    for(int i=0; i<n; i++)
        ans[i]=s.qur(i);
}

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